[洛谷 3181][HAOI2016] 找相同字符【后缀数组+单调栈】
Problem:
题目描述
给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
输入输出格式
输入格式:
两行,两个字符串s1,s2,长度分别为n1,n2。1 <=n1, n2<= 200000,字符串中只有小写字母
输出格式:
输出一个整数表示答案
输入输出样例
输入样例#1:
aabb bbaa
输出样例#1:
10
Solution:
题目要求在两个串 s1, s2 的公共子串数,可以等价于后缀的前缀相同的方案数。
那么我们可以令 s = s1 + s2,即将两个串连接,然后用后缀数组进行后缀排序。
但是我们发现,这样会导致 s2 对 s1 的后缀造成影响。
考虑在 s1 和 s2 之间补一个值最大的字符,将 s1 和 s2 隔开即可。
求出后缀字典序后,我们要怎么快速统计后缀的前缀相同的方案数呢?
考虑到较长的公共前缀包含了更短的公共前缀,所以我们可以用单调栈维护当前的前缀,以快速计算方案数。
Code: O(nlogn), 其中n=|s1|+|s2| [11476K, 840MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 400005; char s[MAXN]; int n1, n, SA[MAXN], rnk[MAXN], ht[MAXN], sum[MAXN]; int stk[MAXN], tops = 0; ll sch[MAXN], ans = 0; inline void buildSA(int m){ int *x = new int[MAXN], *y = new int[MAXN], *cnt = new int[MAXN]; for(register int i = 0; i < m; i++) cnt[i] = 0; for(register int i = 0; i < n; i++) cnt[x[i] = s[i]]++; for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[i]]] = i; for(register int k = 1; k <= n; k <<= 1){ int p = 0; for(register int i = n - k; i < n; i++) y[p++] = i; for(register int i = 0; i < n; i++) if(SA[i] >= k) y[p++] = SA[i] - k; for(register int i = 0; i < m; i++) cnt[i] = 0; for(register int i = 0; i < n; i++) cnt[x[y[i]]]++; for(register int i = 1; i < m; i++) cnt[i] += cnt[i - 1]; for(register int i = n - 1; i >= 0; i--) SA[--cnt[x[y[i]]]] = y[i]; swap(x, y), p = 1, x[SA[0]] = 0; for(register int i = 1; i < n; i++) x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? p - 1 : p++; if(p == n) break; m = p; } for(register int i = 0; i < n; i++) rnk[SA[i]] = i; int k = 0, j; for(register int i = 0; i < n; ht[rnk[i++]] = k) for(k ? k-- : 0, j = SA[rnk[i] - 1]; s[i + k] == s[j + k]; k++); delete []x, delete []y, delete []cnt; } int main(){ scanf("%s", s), n1 = strlen(s), s[n1++] = 123; // Put a sentinel 'z' + 1 to guarantee prefixes of two strings totally apart scanf("%s", s + n1), n = strlen(s + n1) + n1, s[n++] = 96; // Put a sentinel 'a' - 1 for(register int i = 0; i < n; i++) s[i] -= 96; buildSA(28); for(register int i = 1; i < n - 1; i++) sum[i] = sum[i - 1] + (SA[i] < n1); for(register int i = 1; i < n - 1; i++){ while(tops && ht[stk[tops]] > ht[i]) tops--; stk[++tops] = i, sch[tops] = sch[tops - 1] + (ll)(sum[i - 1] - sum[stk[tops - 1] - 1]) * ht[i]; if(SA[i] >= n1) ans += sch[tops]; } tops = 0; for(register int i = 1; i < n - 1; i++) sum[i] = sum[i - 1] + (SA[i] >= n1); for(register int i = 1; i < n - 1; i++){ while(tops && ht[stk[tops]] > ht[i]) tops--; stk[++tops] = i, sch[tops] = sch[tops - 1] + (ll)(sum[i - 1] - sum[stk[tops - 1] - 1]) * ht[i]; if(SA[i] < n1) ans += sch[tops]; } printf("%lld\n", ans); return 0; }
发表评论