1

我查看了网站，但没有直接回答以下问题。

在 C++ 中查找字符串中第 n 次出现的子字符串的最有效方法是什么？

此处的示例显示了如何找到第二个匹配项： http ://www.cplusplus.com/reference/string/string/find/

但是首先找到第一个匹配项，然后使用该位置搜索下一个匹配项等以找到第 n 个匹配项似乎效率很低。如果你想要第25场比赛的位置，有没有更快的方法？

编辑：在更大的上下文中，我正在逐行读取文件，对项目的每个响应都有一个分数，有些则丢失了，得到一个NA字符串。所有项目都用空格分隔。

我想要排除某些项目的选项，所以只能从项目 35 到 80、90 到 120 和 150-200 进行搜索。所以我目前做的是这样的：

string blockedLine(string line)
{
  int b_start[] = {35, 90, 150};
  int b_end[] = {80, 120, 200};
  std::vector<int> space_matches = KMP(line, " ");
  string cuttedLine = "";
  for (int i = 0; i < 3; i++)
    {
      cuttedLine.append(line.substr(space_matches[b_start[i]],
                                    space_matches[b_end[i]]));
    }
  return(cuttedLine);
}

其中KMP一条评论中提到的函数在哪里，它可以让我知道空间出现的位置，并将它们存储在space_matches.

然后我计算NA这个附加字符串中的出现次数。问题是，如果没有这个附加，在大约 200k 行上读取整行只需要 1 秒。当我使用这种附加方法来获取子字符串时，需要 14 秒，这太慢了。

有什么改进可以加快速度？

4

1 回答 1

2 
/// Returns the position of the 'Nth' occurrence of 'find' within 'str'.
/// Note that 1==find_Nth( "aaa", 2, "aa" ) [2nd "aa"]
/// - http://stackoverflow.com/questions/17023302/
size_t find_Nth(
    const std::string & str ,   // where to work
    unsigned            N ,     // N'th ocurrence
    const std::string & find    // what to 'find'
) {
    if ( 0==N ) { return std::string::npos; }
    size_t pos,from=0;
    unsigned i=0;
    while ( i<N ) {
        pos=str.find(find,from);
        if ( std::string::npos == pos ) { break; }
        from = pos + 1; // from = pos + find.size();
        ++i;
    }
    return pos;
/**
    It would be more efficient to use a variation of KMP to
    benefit from the failure function.
    - Algorithm inspired by James Kanze.
    - http://stackoverflow.com/questions/20406744/
*/
}

int main() {
    {
        //                       0123456789.123456789.123
        assert(  3 == find_Nth( "My gorila ate the banana", 1 , "gorila") );
        assert( 18 == find_Nth( "My gorila ate the banana", 1 , "banana") );

        //                       0123456789.123456789.123
        assert(  3 == find_Nth( "My banana ate the banana", 1 , "banana") );
        assert( 18 == find_Nth( "My banana ate the banana", 2 , "banana") );

        assert( std::string::npos == find_Nth( "My banana ate the banana", 3 , "banana") );
        assert( std::string::npos == find_Nth( "My banana ate the banana", 3 , "gorila") );
    }
        assert( 1==find_Nth( "aaa", 2, "aa" ) );
        assert( 0==find_Nth( "aaa", 1, "aa" ) );
    {
        std::string str;
        //     01234567
        str = "aaaaaaaa"; assert( 8==str.size() );
        assert( find_Nth( str, 0 , "aa") == std::string::npos );
        assert( find_Nth( str, 1 , "aa") == 0 );
        assert( find_Nth( str, 2 , "aa") == 1 );
        assert( find_Nth( str, 3 , "aa") == 2 );
        assert( find_Nth( str, 4 , "aa") == 3 );
        assert( find_Nth( str, 5 , "aa") == 4 );
        assert( find_Nth( str, 6 , "aa") == 5 );
        assert( find_Nth( str, 7 , "aa") == 6 );
        assert( find_Nth( str, 8 , "aa") == std::string::npos  );
        assert( find_Nth( str, 9 , "aa") == std::string::npos  );
    }
}
于 2014-12-27T15:33:23.957 回答