我正在C++中編寫一個grep函數(作爲一個自我分配的練習 - 我意識到它沒有實際的grep特性的功能)採取原始字符串和您正在尋找的搜索字符串。在代碼中,我輸入了一個grep字符串中的所有字符,直到它看到的第一個空格。然後我將grep字符串中的字符與搜索字符串進行比較,如果匹配,則將其存儲在一個臨時字符串中。我遍歷grep字符串並將搜索字符串的長度與臨時字符串進行比較以查看它是否匹配。比較字符串大小是比較字符的可接受替代方法嗎?
我的問題:那種形式不好,比較長度?我可以使用for循環來比較每個單獨的字符,但似乎不太會吃掉CPU週期。這裏是我的輸入函數供參考:
std::string grep(std::string originalStr, std::string searchStr)
{
std::string grepStr = "";
std::string finalStr = "";
//stores final string; is the return value
finalStr.resize(originalStr.length() + 1);
grepStr.resize(originalStr.length() + 1);
int place = 0;
//remember where you are in originalStr[place]
int numOfOccurences = 0;
//remember number of times searchStr was found;
//not necessary
std::string tempStr = "";
//will temporarily hold grepStr
//handles case if first occurence is a space
if (originalStr[0] == ' ')
{
place++;
}
while (place != originalStr.length())
{
tempStr = "";
while (originalStr[place] != ' ')
{
if (originalStr[place] == ' ')
{
break;
}
grepStr[place] = originalStr[place];
++place;
}
++place;//ensures you skip over the space next pass
for (int i = 0; i != grepStr.length(); i++)
{
if (grepStr[i] == searchStr[i])
{
//if they are the same, append that char..
tempStr[i] = grepStr[i];
if (tempStr.length() == grepStr.length())
//..then check for string length; if same, searchStr equals tempStr
//and you can append grepStr to the finalStr
{
for (int x = 0; x != finalStr.length(); x++)
{
finalStr[x] = grepStr[x];
}
++numOfOccurences;
//add one to the number of occurences in originalStr
finalStr += ' ';
//add a space IF you find the string
}
}
}
}
return finalStr;
}
我發現鏈接關於Boyer-Moore快速字符串搜索算法非常有趣,謝謝! – 2009-05-18 01:13:42
很高興喜歡它。它確實是一種很酷的算法;真的很違反直覺,你可以做很快的字符串匹配。 – 2009-05-18 02:44:47