本题我们可以考虑成从后往前的匹配，因为要让后缀最多的为0，不妨就是从后往前按照需求的进行匹配即可，这个很好想，就是细节有点多了。
先是讲讲后缀数组的做法，这里不能用倍增的后缀数组，因为还要带一个log，这样要是写的不好可就TLE了，所以这里用线性复杂度的DC3来写这道题，然后求出height，找到需求串的位置。然后按照sa函数的排名从前往后和从后往前的分别去考虑，进行相同前缀的计算，然后算出对应的前缀的长度和最多允许的长度，然后再看看如果一边是满了的时候，可不可以9或者0的进位（如果前面没有进位的时候，就是找0）。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> //#include <unordered_map> //#include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 6e6 + 10; struct DC3 { static const int maxn = 6e6 + 10; #define F(x) ((x)/3+((x)%3==1?0:tb)) #define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2) int sa[maxN], rk[maxN], height[maxN], s[maxN]; int wa[maxn], wb[maxn], wv[maxn], wss[maxn]; inline int c0(int *r, int a, int b) { return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2]; } inline int c12(int k, int *r, int a, int b) { if(k==2) return r[a]<r[b] || (r[a]==r[b] && c12(1,r,a+1,b+1)); else return r[a]<r[b] || (r[a]==r[b] && wv[a+1] < wv[b+1]); } inline void ssort(int *r, int *a, int *b, int n, int m) { int i; for(i=0; i<n; i++) wv[i] = r[a[i]]; for(i=0; i<m; i++) wss[i] = 0; for(i=0; i<n; i++) wss[wv[i]]++; for(i=1; i<m; i++) wss[i] += wss[i-1]; for(i=n-1; i>=0; i--) b[--wss[wv[i]]] = a[i]; } inline void dc3(int *r, int *sa, int n, int m) { int i, j, *rn = r + n; int *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p; r[n] = r[n + 1] = 0; for(i=0;i<n;i++) if(i % 3 != 0) wa[tbc++] = i; ssort(r+2, wa, wb, tbc, m); ssort(r+1, wb, wa, tbc, m); ssort(r, wa, wb, tbc, m); for(p=1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++) rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p - 1 : p++; if(p < tbc) dc3(rn, san, tbc, p); else for(i=0; i<tbc; i++) san[rn[i]] = i; for(i=0; i<tbc; i++) if(san[i]<tb) wb[ta++] = san[i] * 3; if(n % 3 == 1) wb[ta++] = n - 1; ssort(r, wb, wa, ta, m); for(i=0; i<tbc; i++) wv[wb[i]=G(san[i])]=i; for(i=0, j=0, p=0; i<ta && j<tbc; p++) sa[p]=c12(wb[j]%3, r, wa[i], wb[j]) ? wa[i++] : wb[j++]; for(; i<ta; p++) sa[p] = wa[i++]; for(; j<tbc; p++) sa[p] = wb[j++]; } inline void da(int n,int m) { for(int i=n; i<n*3; i++) s[i]=0; dc3(s, sa, n+1, m); int i, j, k=0; for(i=0;i<=n;i++) rk[sa[i]]=i; for(i=0;i<n;i++){ if(k)k--; j=sa[rk[i]-1]; while(s[i+k] == s[j+k])k++; height[rk[i]]=k; } } } sa; char s[maxN]; int N, a[maxN], b[maxN], ans, num0[maxN], num9[maxN]; bool zp[maxN]; int main() { while(scanf("%s", s + 1) != EOF) { int len = (int)strlen(s + 1); for(int i=1; i<=len; i++) a[i] = s[len - i + 1] - '0'; num0[len + 1] = num9[len + 1] = 0; for(int i=len; i>=1; i--) { if(a[i] == 0) num0[i] = num0[i + 1] + 1; else num0[i] = 0; if(a[i] == 9) num9[i] = num9[i + 1] + 1; else num9[i] = 0; } bool zero = true; b[1] = 10 - a[1]; if(b[1] == 10) b[1] = 0; else zero = false; zp[1] = zero; for(int i=2; i<=len; i++) { if(zero) { b[i] = 10 - a[i]; if(b[i] == 10) b[i] = 0; else zero = false; } else b[i] = 9 - a[i]; zp[i] = zero; } sa.s[0] = 12; for(int i=1; i<=len; i++) { sa.s[i] = a[i] + 1; } for(int i=1; i<=len; i++) { sa.s[len + i] = b[i] + 1; } N = len << 1; sa.s[N + 1] = 12; sa.s[N + 2] = 12; sa.da(N + 2, 15); // for(int i=1; i<=N; i++) printf("%d%c", sa.sa[i], i == N ? '\n' : ' '); // for(int i=1; i<=N; i++) printf("%d%c", sa.rk[i], i == N ? '\n' : ' '); // for(int i=1; i<=N; i++) printf("%d%c", sa.height[i], i == N ? '\n' : ' '); int mid_rk = sa.rk[len + 1]; ans = 0; for(int i=mid_rk + 1, H = INF, id, id_pre, id_suff, len_pre, len_suff, tmp; i <= N; i++) { H = min(H, sa.height[i]); if(!H) break; id = sa.sa[i]; if(id > len) continue; id_pre = H; id_suff = id; len_suff = len - id + 1; len_pre = len - len_suff; tmp = min(H, min(len_pre, len_suff)); if(tmp == min(len_pre, len_suff)) { if(len_pre > len_suff) { if(zp[len_suff]) tmp += num0[len_suff + 1]; else tmp += min(num9[len_suff + 1], id - tmp - 1); } else if(len_suff > len_pre) { if(zp[len_pre]) tmp += num0[len_pre + len_pre + 1]; else tmp += num9[len_pre + len_pre + 1]; } } ans = max(ans, tmp); } for(int i=mid_rk - 1, H = sa.height[mid_rk], id, id_pre, id_suff, len_pre, len_suff, tmp; i >= 1; i--) { id = sa.sa[i]; if(id > len) continue; id_pre = H; id_suff = id; len_suff = len - id + 1; len_pre = len - len_suff; tmp = min(H, min(len_pre, len_suff)); if(tmp == min(len_pre, len_suff)) { if(len_pre > len_suff) { if(zp[len_suff]) tmp += num0[len_suff + 1]; else tmp += min(num9[len_suff + 1], id - tmp - 1); } else if(len_suff > len_pre) { if(zp[len_pre]) tmp += num0[len_pre + len_pre + 1]; else tmp += num9[len_pre + len_pre + 1]; } } ans = max(ans, tmp); H = min(H, sa.height[i]); if(!H) break; } printf("%d\n", ans); } return 0; } /* 2872 ans:2 19919 ans:3 91991 ans:3 9199 ans:1 901 ans:1 9901 ans:2 9911 ans:1 2018 ans:1 109 ans:1 9091 ans:2 12080 ans:2 1000 ans:2 9545455 ans:4 95454545455 ans:6 10090 ans:2 15999841 ans:5 */再讲讲exkmp的做法，如果使用扩展kmp的话，我们可以先去一样的处理出本串对于查询串（也就是需求串的）的最大匹配，也就是每个后缀的最长前缀长度，ex数组。然后与后缀数组相同的来去进行判断。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define eps 1e-6 #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; //const int maxN = 100; const int maxN = 1e6 + 7; char A[maxN], B[maxN]; bool Zop[maxN]; int sa[maxN], sb[maxN]; int lena, lenb, num0[maxN], num9[maxN]; int p[maxN], ex[maxN]; //p数组是用来让B串自己匹配自己的 void exkmp() { p[1] = lenb; int x = 1; while(sb[x] == sb[x + 1] && x + 1 <= lenb) x++; //因为我们p[1]是具有一定性，所以我们不能直接用，所以要先暴力求出p[2] p[2] = x - 1; int k = 2; for(int i=3; i<=lenb; i++) { int pp = k + p[k] - 1, L = p[i - k + 1]; //pp实际上是p if(i + L < pp + 1) p[i] = L;//i-k+L<pp-k+1化简后i+L<pp else { int j = pp - i + 1; if(j < 0) j = 0; while(sb[j + 1] == sb[i + j] && i + j <= lenb) j++; p[i] = j; k = i; } } x = 1; while(sa[x] == sb[x] && x <= lenb) x++;//ex[1]并不具有一定性，所以我们暴力求出ex[1] ex[1] = x - 1; k = 1; for(int i=2; i<=lena; i++) { int pp = k + ex[k] - 1, L = p[i - k + 1]; if(i + L < pp + 1) ex[i] = L; else { int j = pp - i + 1; if(j < 0) j = 0; while(sb[j + 1] == sa[i + j] && i + j <= lena && j <= lenb) j++; ex[i] = j; k = i; } } } int main() { while(scanf("%s", A + 1) != EOF) { lena = (int)strlen(A + 1); lenb = lena; for(int i=1; i<=lena; i++) { sa[i] = A[lena + 1 - i] - '0'; } for(int i=lena, pos0 = lena, pos9 = lenb; i>=1; i--) { if(sa[i] == 0) { pos9 = i - 1; } else if(sa[i] == 9) { pos0 = i - 1; } else { pos0 = pos9 = i - 1; } num0[i] = pos0 - i + 1; num9[i] = pos9 - i + 1; } bool zero = true; sb[1] = 10 - sa[1]; if(sb[1] == 10) sb[1] = 0; else zero = false; for(int i=2; i<=lenb; i++) { if(zero) { sb[i] = 10 - sa[i]; if(sb[i] == 10) sb[i] = 0; else zero = false; } else { sb[i] = 9 - sa[i]; } Zop[i] = zero; } exkmp(); // printf("bp: "); for(int i=1; i<=lenb; i++) printf("%d%c", p[i], i == lenb ? '\n' : ' '); // printf("ex: "); for(int i=1; i<=lena; i++) printf("%d%c", ex[i], i == lena ? '\n' : ' '); int ans = 0; for(int i=2, len_pre, len_suff; i<=lena; i++) { len_pre = ex[i]; len_pre = min(len_pre, i - 1); len_suff = lena - i + 1; if(len_pre < i - 1) { if(len_pre >= len_suff) { ans = max(ans, len_pre + min(num9[len_pre + 1], i - 1 - len_pre)); } else { ans = max(ans, len_pre); } } else { if(i + len_pre == lena + 1) ans = max(ans, len_pre); else if(Zop[i + len_pre - 1]) { ans = max(ans, len_pre + num0[i + len_pre]); } else { ans = max(ans, len_pre + num9[i + len_pre]); } } } printf("%d\n", ans); } return 0; } /* 15999841 ans:5 9901 ans:2 95454545455 ans:6 */
