1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
|
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5 + 10, N = 1e5 + 10; queue<int> q; int rt[maxn], ls[maxn * 50], rs[maxn * 50], sum[maxn * 50], cnt; #define mid (l + r) / 2 void up(int &o, int pre, int l, int r, int k) { o = ++cnt; sum[o] = sum[pre] + 1; ls[o] = ls[pre]; rs[o] = rs[pre]; if (l == r) return; if (k <= mid) up(ls[o], ls[pre], l, mid, k); else up(rs[o], rs[pre], mid+ 1, r, k); } int qu(int o, int l, int r, int k) { if (l == r) return sum[o]; if (k <= mid) return qu(ls[o], l, mid, k); return qu(rs[o], mid + 1, r, k); } struct ptree{ char s[maxn]; int next[maxn][26],fail[maxn],cnt[maxn],len[maxn], d[maxn]; int last,n,p; long long res; ll ans = 0; inline int newnode(int l){ cnt[p]=0; len[p]=l; memset(next[p], 0, sizeof(next[p])); return p++; } inline void init(){ n = last = p = ans = 0; newnode(0),newnode(-1); s[n]=-1; fail[0]=1; } inline int FL(int x){ while(s[n-len[x]-1]!=s[n]) x=fail[x]; return x; } void add(char c){ c-='a'; s[++n]=c; int cur=FL(last); if(!next[cur][c]){ int now=newnode(len[cur]+2); cnt[now] = 1; rt[now] = rt[cur]; int FF = next[FL(fail[cur])][c]; fail[now]=next[FL(fail[cur])][c]; next[cur][c]=now; while (FF > 1) { if (qu(rt[now], 1, N, FF)) break; up(rt[now], rt[now], 1, N, FF); FF = fail[FF]; } up(rt[now], rt[now], 1, N, now); ans += sum[rt[now]] - 1; } last=next[cur][c]; } } p; char s[maxn]; int main(){ int T, Case = 0; scanf("%d", &T); while (T--) { scanf("%s",s); p.init(); cnt = 0; for (int i = 0; s[i]; i++) p.add(s[i]); printf("Case #%d: %lldn", ++Case, p.ans); } }
|
近期评论