0

我正在用 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;
}
4

2 回答 2

4

不，一点也不差。毕竟，至少在某种意义上，如果两个字符串的长度不相等，它们就不可能相等。

如果想度过一段美好的时光，请查看 Boyer-Moore 字符串匹配算法和 Knuth-Pratt-Morris 算法。J [原文如此！他真的是这样拼写的]摩尔对他们有一个很好的页面。

于 2009-05-18T01:01:51.177 回答
0

如果您使用std::string，STL find 函数可能会比您创建的这个版本更有效地运行。在字符串中搜索子字符串是一个已知问题，我确信库版本已尽可能优化。

于 2009-05-18T01:05:34.320 回答