Настройки поиска (Страница 1 из 3)

6
3 4 5 1 6 2

          
                         6
                        /  \
                     1      5
                      \     /
                       2   4
                          /
                         3  

                         6
                        /  \
                     1      5
                      \      \
                       2      4
                             /
                            3  

const unsigned long long pr = 97;//97 1039

unsigned long long h[6000], h1, _pow[6000];
char s[5000];
int n, res = 0;

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt","rt",stdin);
        freopen("output.txt","wt",stdout);
    #endif
    scanf("%s", &s); n = strlen(s);
    h[0] = 0; _pow[0] = 1;
    for (int i = 1; i <= n; i++)
        h[i] = h[i - 1] * pr + s[i - 1], _pow[i] = _pow[i - 1] * pr;
    
    for (int k = 1; k <= n; k++)
    {
        vector<unsigned long long> all;
        for (int i = 0; i + k <= n; i++)
        {
            h1 = h[i + k] - h[i] * _pow[k];
            all.pb(h1);
        }
        sort(all.begin(), all.end());
        all.erase (unique (all.begin(), all.end()), all.end());
        res += all.sz;
    }

    printf("%d\n", res);
return 0;
}