4484: The Graver Robbers' Chronicles

题目连接：

http://acm.scu.edu.cn/soj/problem.action?id=4484

Description

One day, Kylin Zhang and Wu Xie are trapped in a graveyard. They find an ancient piece of parchment with a cipher string.

After discussion and analysis, they find the password is the total number of the cipher string's distinct substrings.

Although Kylin Zhang is powerful and always help his friends get rid of danger, this time he is helpless beacause

he is not good at math and programming.

As a smart Acmer, can you help them solve this problem so that they can escape from this horrible graveyard.

Input

The first line is an integer T stands for the number of test cases.

Then T test case follow.

For each test case there is one string.

Constraints:

T is no bigger than 30.

The length of string is no bigger than 50000.

Every string only contains lowercase letters.

Output

For each test case, output the answer in a single line. one number saying the number of distinct substrings.

Sample Input

2

aaaaa

cacac

Sample Output

5

9

Hint

题意

给你一个串，问你有多少个不同的子串

题解：

后缀自动机/后缀数组裸题

枚举结尾的字符的最长后缀，减掉和自己父亲重合的位置就好了。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 50100;

char s1[maxn];

struct SAM {

    struct {

        int len, f, ch[26];

        void init() {

            len = 0, f = -1;

            memset(ch, 0xff, sizeof (ch));

        }

    } e[maxn<<1];

    int idx, last;

    void init() {

        idx = last = 0;

        e[idx++].init();

    }

    int newnode() {

        e[idx].init();

        return idx++;

    }

    void add(int c) {

        int end = newnode();

        int tmp = last;

        e[end].len = e[last].len + 1;

        for (; tmp != -1 && e[tmp].ch[c] == -1; tmp = e[tmp].f) {

            e[tmp].ch[c] = end;

        }

        if (tmp == -1) e[end].f = 0;

        else {

            int nxt = e[tmp].ch[c];

            if (e[tmp].len + 1 == e[nxt].len) e[end].f = nxt;

            else {

                int np = newnode();

                e[np] = e[nxt];

                e[np].len = e[tmp].len + 1;

                e[nxt].f = e[end].f = np;

                for (; tmp != -1 && e[tmp].ch[c] == nxt; tmp = e[tmp].f) {

                    e[tmp].ch[c] = np;

                }

            }

        }

        last = end;

    }

};

SAM sam;

void solve()

{

    scanf("%s",s1);

    int len = strlen(s1);

    sam.init();

    for(int i=0;i<len;i++)

        sam.add(s1[i]-'a');

    long long ans = 0;

    for(int i=1;i<sam.idx;i++)

        ans = ans + sam.e[i].len - sam.e[sam.e[i].f].len;

    printf("%lld\n",ans);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)solve();

    return 0;

}

巴特西

SCOJ 4484 The Graver Robbers' Chronicles 后缀自动机