我要死了。这是我做过的最恶心的题之一。
天下第一的大毒瘤。有gay毒。
我不如熊猫好多年...
题意：给定字符串，求g[i]，表示：[0, i]中满足该子串既是前缀又是后缀还不重叠的子串数。
解：题面都写了KMP，想必跟KMP有关。
然后我痛苦的思考了1天无果......
我首先想到求出nex[]和f[]，f[]表示可重叠的既是前缀又是后缀的子串数。
然后想找出f[]和g[]的关系，失败。
然后想到再来一个len[]表示f[]最长的那一个的长度，还是不行...
被折磨了一天，撑不住了，在吃完饭的时候开始看题解。
发现：我们要魔改KMP，每次跳完增加之后若大于一半，就再跳...
这时你停住的地方j就是恰好比一半小的最大值。
然后如果i这里的nex为0，j显然为0，g[]显然也为0
否则j不为0，这时你把f[j - 1]加1就是g[i]
你加的1就是[0, j - 1]这个串。
然后j可以直接继承到下一个i
因为你的j和KMP里的j差不多，除了不超过一半之外都一样。
然后你i每次 + 1的时候g[]最多 + 1
这样就搞过了这个大毒瘤题....
(事实上还不是很清楚)
1 #include2 #include 3 4 typedef long long LL; 5 6 const int N = 1000010, MO = 1e9 + 7; 7 8 int nex[N], f[N], g[N]; 9 char s[N];10 11 inline void solve() {12 scanf("%s", s);13 int n = strlen(s);14 nex[0] = 0;15 f[0] = 0;16 for(int i = 1, j = 0; i < n; i++) {17 while(j && s[i] != s[j]) {18 j = nex[j - 1];19 }20 if(s[i] == s[j]) {21 j++;22 }23 nex[i] = j;24 if(j) {25 f[i] = f[j - 1] + 1;26 }27 else {28 f[i] = 0;29 }30 }31 32 g[0] = 0;33 LL ans = 1;34 for(int i = 1, j = 0; i < n; i++) {35 while(j && s[i] != s[j]) {36 j = nex[j - 1];37 }38 if(s[i] == s[j]) {39 j++;40 }41 while(2 * j > (i + 1)) {42 j = nex[j - 1];43 }44 if(!j) {45 g[i] = 0;46 }47 else {48 g[i] = f[j - 1] + 1;49 }50 ans = (ans * (g[i] + 1)) % MO;51 }52 printf("%lld\n", ans);53 return;54 }55 56 int main() {57 int T;58 scanf("%d", &T);59 while(T--) {60 solve();61 }62 return 0;63 }
[update]首先有个30分暴力想必大家都会。
说一下SAM做法。你考虑一个border是什么样的，显然前缀是一条链，而后缀是该点在fail树上到根的链。于是相当于求这两个东西的交，还有个深度限制。
给前缀链标记为1，非前缀标记为0，并统计到根路径的点权和。这样，我们只要找到每个点在fail树上满足限制的最深的点，就能知道答案了。
考虑到每个点在fail树上向下走的时候，满足限制的最深点也是单调向下的。于是拿一个栈维护当前点到根的链，用一个单调指针在栈上找就行了。
1 #include2 3 #define add(x, y) edge[++tp].v = y; edge[tp].nex = e[x]; e[x] = tp 4 5 const int N = 2000010, MO = 1e9 + 7; 6 7 struct Edge { 8 int nex, v; 9 }edge[N]; int tp; 10 11 int n, tr[N][26], fail[N], len[N], e[N], vis[N], Time, val[N], stk[N], top, ans, tot = 1, last = 1; 12 char str[N]; 13 std::queue Q; 14 /* 15 2 16 abcababc 17 abcababc 18 */ 19 namespace bf { 20 typedef unsigned long long uLL; 21 const uLL B = 131; 22 uLL pw[300], h[300]; 23 inline void prework() { 24 pw[0] = 1; 25 for(int i = 1; i <= n; i++) { 26 pw[i] = pw[i - 1] * B; 27 h[i] = h[i - 1] * B + str[i]; 28 } 29 return; 30 } 31 inline uLL Hash(int l, int r) { 32 return h[r] - h[l - 1] * pw[r - l + 1]; 33 } 34 inline void solve() { 35 prework(); 36 int ans = 1; 37 for(int i = 1; i <= n; i++) { 38 /// [1, i] 39 //printf("i = %d \n", i); 40 int temp = 1; 41 for(int t = i >> 1; t; t--) { 42 //printf("t = %d \n", t); 43 if(Hash(1, t) == Hash(i - t + 1, i)) { 44 /// num[i] = t; 45 ++temp; 46 } 47 } 48 ans = 1ll * ans * temp % MO; 49 } 50 printf("%d\n", ans); 51 return; 52 } 53 } 54 55 inline void insert(int f) { 56 int p = last, np = ++tot; 57 last = np; 58 len[np] = len[p] + 1; 59 vis[np] = Time; 60 while(p && !tr[p][f]) { 61 tr[p][f] = np; 62 p = fail[p]; 63 } 64 if(!p) { 65 fail[np] = 1; 66 } 67 else { 68 int Q = tr[p][f]; 69 if(len[Q] == len[p] + 1) { 70 fail[np] = Q; 71 } 72 else { 73 int nQ = ++tot; 74 len[nQ] = len[p] + 1; 75 fail[nQ] = fail[Q]; 76 fail[Q] = fail[np] = nQ; 77 memcpy(tr[nQ], tr[Q], sizeof(tr[Q])); 78 while(tr[p][f] == Q) { 79 tr[p][f] = nQ; 80 p = fail[p]; 81 } 82 } 83 } 84 return; 85 } 86 87 inline void clear() { 88 for(register int i(1); i <= tot; i++) { 89 memset(tr[i], 0, sizeof(tr[i])); 90 val[i] = e[i] = fail[i] = len[i] = 0; 91 } 92 last = tot = 1; 93 tp = 0; 94 return; 95 } 96 97 void DFS(int x, int p) { 98 stk[++top] = x; 99 /// calc ans x100 //printf("x = %d \n", x);101 while(p < top && len[stk[p + 1]] * 2 <= len[x]) {102 ++p;103 }104 if(vis[x] == Time) {105 ans = 1ll * ans * (val[stk[p]] + 1) % MO;106 }107 for(int i = e[x]; i; i = edge[i].nex) {108 int y = edge[i].v;109 val[y] = val[x] + (vis[y] == Time);110 DFS(y, p);111 }112 --top;113 return;114 }115 116 inline void solve() {117 scanf("%s", str + 1);118 n = strlen(str + 1);119 /*if(n <= 200) {120 bf::solve();121 return;122 }*/123 ++Time;124 ans = 1;125 for(register int i(1); i <= n; i++) {126 insert(str[i] - 'a');127 }128 for(register int i(2); i <= tot; i++) {129 add(fail[i], i);130 }131 132 DFS(1, 1); /// get val133 printf("%d\n", ans);134 clear();135 return;136 }137 138 int main() {139 int T;140 scanf("%d", &T);141 while(T--) {142 solve();143 if(T) memset(str + 1, 0, n * sizeof(char));144 }145 return 0;146 }
这题非常良心的没卡空间。