模板--后缀自动机

it2022-05-06  0

你没有看错,菜鸡退役前刚学后缀自动机 #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<queue> #define ll long long #define M 2000010 #define mmp make_pair using namespace std; int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f; } int fa[M], ch[M][26], len[M], sz[M], t[M], a[M], lst = 1, cnt = 1; char s[M]; void insert(int c) { int f = lst, p = ++cnt; lst = p; len[p] = len[f] + 1; sz[p] = 1; while(f && !ch[f][c]) ch[f][c] = p, f = fa[f]; if(!f) { fa[p] = 1; return; //情况1 } int q = ch[f][c], nq = ++cnt; if(len[f] + 1 == len[q]) { fa[p] = q; cnt--; //情况二 max = min - 1 return; } // 情况3 有中转 len[nq] = len[f] + 1; fa[nq] = fa[q]; fa[q] = fa[p] = nq; memcpy(ch[nq], ch[q], sizeof(ch[nq])); while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f]; } int main() { scanf("%s", s + 1); int le = strlen(s + 1); for(int i = 1; i <= le; i++) insert(s[i] - 'a'); for(int i = 1; i <= cnt; i++) t[len[i]]++; for(int i = 1; i <= cnt; i++) t[i] += t[i - 1]; for(int i = 1; i <= cnt; i++) a[t[len[i]]--] = i; ll ans = 0; for(int i = cnt; i >= 1; i--) { int now = a[i]; sz[fa[now]] += sz[now]; if(sz[now] > 1) ans = max(ans, 1ll * sz[now] * len[now]); } cout << ans << "\n"; return 0; }

转载于:https://www.cnblogs.com/luoyibujue/p/10596504.html


最新回复(0)