SP694 DISUBSTR - Distinct Substrings
求本质不同的子串数量。
考虑容斥：对于rk[i] 与 rk[i -1]他们的lcp就是会重复出现的子串数量。就是这段会被重复计算在两个人的前缀中，所以减去。
对于rk[i] 和 rk[i - 2]会被减掉在rk[i - 1]
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e3 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } void solve() { int ca;ca = read(); while(ca--) { scanf("%s",s + 1); n = strlen(s + 1); m = 122; SA(); LCP(); LL ans = 1LL * n * (n + 1) / 2; for(int i = 1;i <= n;++i) ans -= height[i]; printf("%lld ",ans); } } int main() { solve(); //system("pause"); return 0; }
P2870 [USACO07DEC]Best Cow Line G
显然这题有一个思路就是从两端贪心取，如果一样就比较里面，一直比到不一样。
比较的操作暴力复杂度过高，我们可以发现，这个过程其实就是比较原串的后缀和原串反转之后的后缀的大小。
我们可以把原串反转接入原串的结尾，注意在中间插入一个无穷小字符，这样不影响后缀排序。然后直接比较rk就行了。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e6 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } vector<char> ans; void solve() { n = read(); string t; for(int i = 1;i <= n;++i) { char c;scanf("%c",&c); getchar(); t += c; } string ss = t; ss += 'A' - 1; reverse(t.begin(),t.end()); ss += t; n = ss.size(); m = 122; for(int i = 1;i <= n;++i) s[i] = ss[i - 1]; SA(); LCP(); int L = 1,r = (n - 1) / 2,tot = 0; while(L <= r) { //printf("L is %d r is %d rk[L] is %d rk[r] is %d ",L,r,rk[L],rk[n - r + 1]); if(rk[L] <= rk[n - r + 1]) printf("%c",s[L++]); else printf("%c",s[r--]); ++tot; if(tot == 80) printf(" "),tot = 0; } } int main() { solve(); system("pause"); return 0; }
P4051 [JSOI2007]字符加密
这题其实不难：就是对环形字符串进行一下后缀排序就可以了。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 2e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } vector<pii> vec; bool cmp(pii a,pii b) { return a.first < b.first; } void solve() { string t;cin >> t; t += t; n = t.size(); for(int i = 1;i <= n;++i) s[i] = t[i - 1]; m = 122; SA(); LCP(); int x = n / 2; for(int i = 1;i <= x;++i) { vec.push_back(pii{rk[i],i}); } sort(vec.begin(),vec.end(),cmp); for(auto v : vec) { printf("%c",s[v.second + x - 1]); } } int main() { solve(); system("pause"); return 0; }
P2852 [USACO06DEC]Milk Patterns G
求可重叠的出现至少k次的子串。
对于连续的k - 1个rk，他们的min(height)就是他们出现的最小重叠子串。
我们求一下所有的连续k - 1的min(height)的max即可。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 2e4 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } int a[N],b[N]; deque<int> Q; void solve() { int k;n = read(),k = read(); for(int i = 1;i <= n;++i) a[i] = read(),b[i] = a[i]; sort(b + 1,b + n + 1); int len = unique(b + 1,b + n + 1) - b - 1; for(int i = 1;i <= n;++i) { a[i] = lower_bound(b + 1,b + len + 1,a[i]) - b; } for(int i = 1;i <= n;++i) s[i] = a[i]; m = 122; SA(); LCP(); k--; int ans = 0; for(int i = 1;i <= n;++i) { while(!Q.empty() && i - Q.front() >= k) Q.pop_front(); while(!Q.empty() && height[Q.back()] >= height[i]) Q.pop_back(); Q.push_back(i); if(i >= k) ans = max(ans,height[Q.front()]); } printf("%d ",ans); } int main() { solve(); system("pause"); return 0; }
P4248 [AHOI2013]差异
这里我们前面的两个的和还是很好处理的，主要是求后面的那个lcp。
考虑后缀排序之后的所有后缀：因为对于两个后缀lcp(x,y) = min{height[i]} (i = [x,y])
那么我们可以考虑每个height的贡献，很显然height的贡献就是一段区间满足里面的都height都>=他，那么这个区间内的任意横跨i的子区间都满足条件。
这是个很经典的维护操作，我们考虑单调栈维护出L[i]表示左边<=他的最小的位置，r[i]表示右边<他的最小的位置，这里我们右边不取到等号，是因为防止端点重复计算。
然后横跨的区间数量就是左半边任选一点 * 右半边任选一点的方案数。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } stack<int> S; LL dp[N]; void solve() { scanf("%s",s + 1); m = 122; n = strlen(s + 1); SA(); LCP(); LL ans = 1LL * n * (n + 1) * (n - 1) / 2; for(int i = 1;i <= n;++i) { int t = 0; while(!S.empty() && height[S.top()] > height[i]) S.pop(); if(!S.empty()) t = S.top(); dp[i] = dp[t] + 1LL * (i - t) * height[i]; ans -= dp[i] * 2LL; S.push(i); } printf("%lld ",ans); } int main() { solve(); system("pause"); return 0; }
P3181 [HAOI2016]找相同字符
这里其实和上面一题很像：首先很显然考虑容斥。
字符串拼接之后产生的相同子串数量 - 没拼接前产生的相同子串数量。
那么主要问题就变成了求相同子串数量。因为这里没有规定长度，显然对于任意的height都满足条件。
那么问题也就变成了求$sum_{i = 1}^{n}sum_{j = i + 1}^{n}lcp(i,j)$
那么就是上题是一样的东西了。注意中间特殊字符拼接。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } stack<int> S; int L[N],r[N]; LL query() { n = strlen(s + 1); m = 122; SA(); LCP(); while(!S.empty()) S.pop(); LL ans = 0; for(int i = 1;i <= n;++i) L[i] = i - 1,r[i] = i + 1; for(int i = 1;i <= n;++i) { while(!S.empty() && height[S.top()] > height[i]) { r[S.top()] = i; S.pop(); } if(!S.empty()) L[i] = S.top(); S.push(i); } while(!S.empty()) r[S.top()] = n + 1,S.pop(); for(int i = 2;i <= n;++i) ans += 1LL * (i - L[i]) * (r[i] - i) * height[i]; //dbg(ans); return ans; } void solve() { string s1,s2;cin >> s1 >> s2; for(int i = 1;i <= s1.size();++i) s[i] = s1[i - 1]; LL ma1 = query(); for(int i = 1;i <= s2.size();++i) s[i] = s2[i - 1]; s[s2.size() + 1] = ' '; LL ma2 = query(); s1 += 'A' - 1; s1 += s2; for(int i = 1;i <= s1.size();++i) s[i] = s1[i - 1]; s[s1.size() + 1] = ' '; LL ans = query() - ma1 - ma2; printf("%lld ",ans); } int main() { solve(); system("pause"); return 0; }
P4070 [SDOI2016]生成魔咒
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int s[N],b[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } struct Node{int L,r,mi;}node[N << 2]; void Pushup(int idx) {node[idx].mi = min(node[idx << 1].mi,node[idx << 1 | 1].mi);} void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r,node[idx].mi = INF; if(L == r) { node[idx].mi = height[L]; return; } int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); Pushup(idx); } int query(int L,int r,int idx) { if(node[idx].L >= L && node[idx].r <= r) return node[idx].mi; int mid = (node[idx].L + node[idx].r) >> 1,ans = INF; if(mid >= L) ans = min(ans,query(L,r,idx << 1)); if(mid < r) ans = min(ans,query(L,r,idx << 1 | 1)); return ans; } set<int> S; void solve() { n = read(); for(int i = n;i >= 1;--i) s[i] = read(),b[i] = s[i]; sort(b + 1,b + n + 1); int len = unique(b + 1,b + n + 1) - b - 1; for(int i = n;i >= 1;--i) { int pos = lower_bound(b + 1,b + len + 1,s[i]) - b; s[i] = pos; } m = 122; SA(); LCP(); build(1,n,1); LL ans = 0; for(int i = n;i >= 1;--i) { S.insert(rk[i]); int pre = -1,nxt = -1; auto it = S.lower_bound(rk[i]); if(it != S.begin()) pre = *(--it); it = S.upper_bound(rk[i]); if(it != S.end()) nxt = *it; ans += n - i + 1; if(pre != -1) ans -= query(pre + 1,rk[i],1); if(nxt != -1) ans -= query(rk[i] + 1,nxt,1); if(pre != -1 && nxt != -1) ans += query(pre + 1,nxt,1); printf("%lld ",ans); } } int main() { solve(); system("pause"); return 0; }
ST表:
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int s[N],b[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } int f[N][20],lg[N]; set<int> S; void init() { lg[1] = 0;for(int i = 2;i <= n;++i) lg[i] = lg[i >> 1] + 1; for(int i = 1;i <= n;++i) f[i][0] = height[i]; for(int j = 1;j <= 19;++j) { for(int i = 1;i <= n && i + (1 << j) - 1 <= n;++i) { f[i][j] = min(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]); } } } int query(int x,int y) { int k = lg[y - x + 1]; return min(f[x][k],f[y - (1 << k) + 1][k]); } void solve() { n = read(); for(int i = n;i >= 1;--i) s[i] = read(),b[i] = s[i]; sort(b + 1,b + n + 1); int len = unique(b + 1,b + n + 1) - b - 1; for(int i = n;i >= 1;--i) { int pos = lower_bound(b + 1,b + len + 1,s[i]) - b; s[i] = pos; } m = 122; SA(); LCP(); init(); LL ans = 0; for(int i = n;i >= 1;--i) { S.insert(rk[i]); int pre = -1,nxt = -1; auto it = S.lower_bound(rk[i]); if(it != S.begin()) pre = *(--it); it = S.upper_bound(rk[i]); if(it != S.end()) nxt = *it; ans += n - i + 1; if(pre != -1) ans -= query(pre + 1,rk[i]); if(nxt != -1) ans -= query(rk[i] + 1,nxt); if(pre != -1 && nxt != -1) ans += query(pre + 1,nxt); printf("%lld ",ans); } } int main() { solve(); system("pause"); return 0; }
SP1811 LCS - Longest Common Substring
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } stack<int> S; int f[N][20]; int lg[N],st,r[N],L[N]; void init() { lg[1] = 0;for(int i = 2;i <= n;++i) lg[i] = lg[i >> 1] + 1; for(int i = 1;i <= n;++i) f[i][0] = height[i]; for(int j = 1;j <= 19;++j) { for(int i = 1;i <= n && i + (1 << j) - 1 <= n;++j) { f[i][j] = min(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]); } } } void solve() { string s1,s2;cin >> s1 >> s2; st = s1.size(); s1 += 'A' - 1; s1 += s2; n = s1.size(); for(int i = 1;i <= n;++i) s[i] = s1[i - 1]; m = 122; SA(); LCP(); int ans = 0; for(int i = 2;i <= n;++i) { if(sa[i] <= st && sa[i - 1] > st || sa[i] > st && sa[i - 1] <= st) ans = max(ans,height[i]); } printf("%d ",ans); } int main() { solve(); system("pause"); return 0; }
SP705 SUBST1 - New Distinct Substrings
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e4 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } void solve() { int ca;ca = read(); while(ca--) { scanf("%s",s + 1); n = strlen(s + 1); m = 122; SA(); LCP(); LL ans = 1LL * n * (n + 1) / 2; for(int i = 1;i <= n;++i) ans -= height[i]; printf("%lld ",ans); } } int main() { solve(); //system("pause"); return 0; }
P5341 [TJOI2019]甲苯先生和大中锋的字符串
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 2e4 + 5; const double eps = 1e-10; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;int x = 0;char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} char s[N]; int x[N],y[N],c[N],sa[N],rk[N],height[N],n,m; void SA() { memset(c,0,sizeof(c)); for(int i = 1;i <= n;++i) x[i] = s[i],c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[i]]--] = i; for(int k = 1;k <= n;k = (k << 1)) { int num = 0; for(int i = n - k + 1;i <= n;++i) y[++num] = i; for(int i = 1;i <= n;++i) { if(sa[i] > k) { y[++num] = sa[i] - k; } } for(int i = 1;i <= m;++i) c[i] = 0; for(int i = 1;i <= n;++i) c[x[i]]++; for(int i = 2;i <= m;++i) c[i] += c[i - 1]; for(int i = n;i >= 1;--i) sa[c[x[y[i]]]--] = y[i],y[i] = 0; swap(x,y); num = 1,x[sa[1]] = 1; for(int i = 2;i <= n;++i) { if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) x[sa[i]] = num; else x[sa[i]] = ++num; } if(num == n) break; m = num; } } void LCP() { int k = 0; for(int i = 1;i <= n;++i) rk[sa[i]] = i; for(int i = 1;i <= n;++i) { if(rk[i] == 1) { height[1] = 0; continue; } if(k) k--; int j = sa[rk[i] - 1]; while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; height[rk[i]] = k; } } int f[N][20],lg[N]; void init() { lg[1] = 0;for(int i = 2;i <= n;++i) lg[i] = lg[i >> 1] + 1; for(int i = 1;i <= n;++i) f[i][0] = height[i]; for(int j = 1;j <= 19;++j) { for(int i = 1;i <= n && i + (1 << j) - 1 <= n;++i) { f[i][j] = min(f[i][j - 1],f[i + (1 << (j - 1))][j - 1]); } } } int query(int x,int y) { if(x == y) return height[x]; int k = lg[y - x + 1]; return min(f[x][k],f[y - (1 << k) + 1][k]); } int cnt[N]; void solve() { int ca;ca = read(); while(ca--) { string s1;cin >> s1; n = s1.size(); for(int i = 1;i <= n;++i) s[i] = s1[i - 1]; int k;k = read(); m = 122; SA(); LCP(); height[n + 1] = 0; init(); memset(cnt,0,sizeof(cnt)); for(int i = 1;i <= n && i + k - 1 <= n;++i) { int L = i,r = i + k - 1,lx,rx; if(L + 1 > r) rx = n - sa[r] + 1; else rx = query(L + 1,r); lx = max(height[L],height[r + 1]) + 1; // printf("lx is %d rx is %d ",lx,rx); if(lx <= rx) cnt[lx]++,cnt[rx + 1]--; } for(int i = 1;i <= n;++i) cnt[i] += cnt[i - 1]; int mx = 1,ans = -1; for(int i = 1;i <= n;++i) { mx = max(mx,cnt[i]); if(cnt[i] >= mx) { ans = i; } } printf("%d ",ans); } } int main() { solve(); system("pause"); return 0; }