считать число вхождений каждой подстроки?
Учитывая строку S, Я хочу рассчитать количество подстрок, которые произошли N раз (1 <= n <= s.length ()). Я сделал это с переходящий хэш, это можно сделать с помощью дерева суффиксов. Как это можно решить, используя массив суффиксов со сложностью O (n ^ 2)?
как для s = «ababaab»
№ строки
4 1 «a» (подстрока «a» присутствует 4 раза)
3 2 «b», «ab» (подстрока «b» и «ab» присутствуют 3 раза)
2 2 «ба», «аба»
1 14 «аа», «баб», «баа», «ааб», «ааб» ….
Решение
Это не форум для получения бесплатного кода, но так как я был в таком хорошем моде, я написал короткий пример для вас. Но я не могу гарантировать, что это без ошибок, это было написано в течение 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;
}
Другие решения