Оптимизация алгоритма совпадение строки


Я пытался решить эту проблему. Я подумал о возможной связи между количеством матчей среди последующих подстроки, но не мог найти. Так, наверное, наивные решения, что я был подготовлен:

#include <iostream>
#include <cstring>

using namespace std;

int n;
char str[1000000];

int sim(int i, int len)
{
    int j=0;
    for(; i<len; i++, j++)
    {
        if(str[i]!=str[j])
            return j;
    }
    return j;
}

void solve()
{
    int len=strlen(str);
    int count=len;

    for(int i=1; i<len; i++)
    {
        count+=sim(i, len);
    }
    cout<<count<<endl;
}

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>str;
        solve();
    }

    return 0;
}

Сейчас представления на interviewstreet говорит, что я прошел 7/10 тесткейсам но лимит времени превышен на 8 тестах! Это означает, что мое решение не настолько наивна, но она также указывает на необходимость некоторой оптимизации. Вы можете, пожалуйста, подсказать какой-либо способ, чтобы оптимизировать его?



Комментарии
1 ответ

Я думаю, что вам нужно-это суффиксное дерево: http://en.wikipedia.org/wiki/Suffix_tree. Я действительно не помню много о нем, за исключением того, что она существует и, кажется, имеющих отношение к проблеме под рукой.

Стиль мудрый, я рекомендую пробелы вокруг операторов, как < и << и +=

5
ответ дан 12 декабря 2011 в 02:12 Источник Поделиться