подсчитать количество вхождений каждой подстроки?

Имея строку S, я хочу вычислить количество подстрок, которые встречаются n раз (1 ‹= n ‹= s.length()). Я сделал это с помощью катящегося хэша, это можно сделать с помощью суффиксного дерева. Как это можно решить, используя массив суффиксов сложности O(n^2)?

как для s = "ababaab"

n номер строки

4 1 "a" (подстрока "a" присутствует 4 раза)

3 2 "b" , "ab" (подстрока "b" и "ab" присутствует 3 раза)

2 2 "ба", "аба"

1 14 «аа», «баб», «баа», «ааб», «абаб»...


c++ string suffix-tree suffix-array
person rishabh    schedule 11.06.2015    source источник
comment
Я бы посоветовал вам добавить тег языка программирования к вашему вопросу. Так вы с большей вероятностью получите ответ на свой вопрос. В настоящее время я не уверен, какой язык программирования вы используете.   -  person Roan    schedule 11.06.2015
comment
Я предлагаю вам добавить пример того, как будут выглядеть эти строки, с кратким объяснением того, как обрабатывать эти строки, потому что мне трудно понять, чего вы пытаетесь достичь.   -  person BufferOverflow    schedule 11.06.2015
comment
Я предлагаю вам попробовать себя, потому что это не сайт для меня!   -  person Lightness Races in Orbit    schedule 12.06.2015

Ответы (1)


arrow_upward
2
arrow_downward

Это не форум для получения бесплатного кода, но поскольку я был в таком хорошем моде этим вечером, я написал для вас короткий пример. Но я не могу гарантировать, что это безошибочно, это было написано за 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;

}

person BufferOverflow    schedule 11.06.2015