给定一个字符串 S,我想计算出现 n 次的子字符串的数量 (1 <= n <= s.length())。我已经用rolling hash完成了,它可以通过使用后缀树来完成。如何使用复杂度为 O( n^2 ) 的后缀数组来解决?
比如 s = "ababaab"
n 个字符串
4 1 "a"(子字符串 "a"出现了 4 次)
3 2 "b", "ab"(子字符串 "b"和 "ab"出现了 3 次)
2 2 "ba", "aba"
1 14 "aa", "bab", "baa", "aab", "abab"....
最佳答案
这不是一个获取免费代码的论坛,但由于我今晚的模组非常好,所以我为您写了一个简短的示例。但我不能保证没有错误,这是在 15 分钟内写的,没有特别多的想法。
#include <iostream>
#include <cstdlib>
#include <map>
class CountStrings
{
private:
const std::string text;
std::map <std::string, int> occurrences;
void addString ( std::string );
void findString ( std::string );
public:
CountStrings ( std::string );
std::map <std::string, int> count ( );
};
void CountStrings::addString ( std::string text)
{
std::map <std::string, int>::iterator iter;
iter = ( this -> occurrences ).end ( );
( this -> occurrences ).insert ( iter, std::pair <std::string, int> ( text, 1 ));
}
void CountStrings::findString ( std::string text )
{
std::map <std::string, int>::iterator iter;
if (( iter = ( this -> occurrences ).find ( text )) != ( this -> occurrences ).end ( ))
{
iter -> second ++;
}
else
{
this -> addString ( text );
}
}
CountStrings::CountStrings ( std::string _text ) : text ( _text ) { }
std::map <std::string, int> CountStrings::count ( )
{
for ( size_t offset = 0x00; offset < (( this -> text ).length ( )); offset ++ )
{
for ( size_t length = 0x01; length < (( this -> text ).length ( ) - ( offset - 0x01 )); length ++ )
{
std::string subtext;
subtext = ( this -> text ).substr ( offset, length );
this -> findString ( subtext );
}
}
return ( this -> occurrences );
}
int main ( int argc, char **argv )
{
std::string text = "ababaab";
CountStrings cs ( text );
std::map <std::string, int> result = cs.count ( );
for ( std::map <std::string, int>::iterator iter = result.begin ( ); iter != result.end ( ); ++ iter )
{
std::cout << iter -> second << " " << iter -> first << std::endl;
}
return EXIT_SUCCESS;
关于c++ - 计算每个子串出现的次数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30787975/