常见的子串
| 时间限制： 5000MS | 内存限制： 65536K | |
| 提交总数： 11942 | 接受： 4051 |
描述
字符串T的子字符串被定义为：
给定两个字符串A，B和一个整数K，我们定义S，一组三元组（i，j，k）：
你要给的价值| S | 特定甲，乙和?。
输入
输入文件包含几个数据块。对于每个块，第一行包含一个整数?，随后包含字符串两行阿和乙分别。输入文件以K = 0 结尾。
1≤| A |，| B | ≤10 5
1≤ ? ≤ 分钟 {| A |，| B |} A和B的
字符都是拉丁字母。
产量
对于每种情况，输出一个整数| S |。
示例输入
2 aababaa abaabaa 1 XX XX 0
示例输出
22 五
蜜汁翻译。。额不要在意
挺难的一题，弱弱的我码了一个中午
首先后缀数组双串匹配，同样的操作，两串链接用一字符隔开，跑一遍sa
重点就是如何求出公共前缀大于等于K的子串数
首先如果lcp(i,j) = len 【len >ｋ】那么len - 1也满足
所以对于lcp(i,j)，它的贡献是len - k + 1
我们利用height数组分组，每一个组内的AB串都可以匹配，统计答案即可
但这样会T，因为这样做其实是O(n^2)的
怎么办呢？
我们需要维护一个单调栈，扫两次
第一次：对于每个A，统计它前面的B对于答案的贡献
我们知道两串在height数组之间的最小值即为其最长公共前缀长度，
对于A前第一个B之后的一个最小值，一定会影响到之前左右的B，但是B与B之间的最小值只会影响到前面的B而不影响到后面的B
因此我们维护一个单调递增单调栈，如果当前height比栈顶小，那么栈顶所对应的那些后缀会受到此height的影响【 因为之前的B到后面的A一定会跨过这个地方，而这个地方height较小】，就合并栈顶【注意是合并】
看代码吧
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 200005,maxm = 100005,INF = 1000000000;
inline int RD(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}return out * flag;
}
char s[maxn],B[maxn];
int sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],c[maxn],n,m,K,lA;
void SA(){int *x = t1,*y = t2;for (int i = 0; i <= m; i++) c[i] = 0;for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;for (int i = 1; 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 <<= 1){int p = 0;for (int i = n - k + 1; i <= n; i++) y[++p] = i;for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k;for (int i = 0; i <= m; i++) c[i] = 0;for (int i = 1; i <= n; i++) c[x[y[i]]]++;for (int i = 1; i <= m; i++) c[i] += c[i - 1];for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];swap(x,y);p = 1; x[sa[1]] = 1;for (int i = 2; i <= n; i++)x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;if (p >= n) break;m = p;}REP(i,n) rank[sa[i]] = i;int k = 0;REP(i,n){if (k) k--;int j = sa[rank[i] - 1];while (s[i + k] == s[j + k]) k++;height[rank[i]] = k;}
}
pair<int,int> st[maxn];
int top;
LL ans;
void solve(){LL sum = 0; top = 0;for (int i = 2; i <= n; i++){if (height[i] < K){top = 0; sum = 0;}else {int num = 0;if (sa[i - 1] > lA + 1) num++,sum += height[i] - K + 1;while (top && height[i] <= st[top].first){sum -= st[top].second * (st[top].first - height[i]);num += st[top--].second;}st[++top] = make_pair(height[i],num);if (sa[i] <= lA) ans += sum;}}top = 0; sum = 0;for (int i = 2; i <= n; i++){if (height[i] < K){top = 0; sum = 0;}else {int num = 0;if (sa[i - 1] <= lA) num++,sum += height[i] - K + 1;while (top && height[i] <= st[top].first){sum -= st[top].second * (st[top].first - height[i]);num += st[top--].second;}st[++top] = make_pair(height[i],num);if (sa[i] > lA + 1) ans += sum;}}
}
int main(){while (K = RD()){scanf("%s",s + 1); lA = strlen(s + 1); strcat(s + 1,"#");scanf("%s",B + 1); strcat(s + 1,B + 1);ans = 0; m = 256; n = strlen(s + 1);SA();solve();printf("%lld\n",ans);}return 0;
}