求不同子串个数
裸的后缀自动机
- #include <cstring> #include < cmath > #include < iostream > #include < algorithm > #include < cstdio >
- #define ll long long#define N 2000007 using namespace std;
- inline int read() {
- int x = 0,
- f = 1;
- char ch = getchar();
- while (!isdigit(ch)) {
- if (ch == - ) f = -1;
- ch = getchar();
- }
- while (isdigit(ch)) {
- x = (x << 1) + (x << 3) + ch - 0;
- ch = getchar();
- }
- return x * f;
- }
- int n;
- ll ans;
- struct sam {
- int last,
- cnt;
- int c[N][26],
- fa[N],
- mx[N];
- sam() {
- last = cnt = 1;
- }
- void extend(int x) {
- int p = last,
- np = last = ++cnt;
- mx[np] = mx[p] + 1;
- while (p && !c[p][x]) {
- c[p][x] = np;
- p = fa[p];
- }
- if (!p) fa[np] = 1;
- else {
- int q = c[p][x];
- if (mx[q] == mx[p] + 1) fa[np] = q;
- else {
- int nq = ++cnt;
- mx[nq] = mx[p] + 1;
- memcpy(c[nq], c[q], sizeof(c[q]));
- fa[nq] = fa[q];
- fa[q] = fa[np] = nq;
- while (c[p][x] == q) c[p][x] = nq,
- p = fa[p];
- }
- }
- }
- }
- sam;
- char s[N];
- int main() {
- scanf("%s", s + 1);
- n = strlen(s + 1);
- for (int i = 1; i <= n; i++) sam.extend(s[i] - a);
- for (int i = 1; i <= sam.cnt; i++) ans += sam.mx[i] - sam.mx[sam.fa[i]];
- printf("%lld", ans);
- }
来源: http://www.bubuko.com/infodetail-2514739.html