传送门：http://poj.org/problem?id=3415
题意：给定两个串，求长度不小于 k 的公共子串的个数
解题思路：
常用技巧，通过在中间添加特殊标记符连接两个串，把两个串的问题转换为 一个串的问题
按照 height 分组。
这里有两种情况
一、后缀排名中， B的后缀在后 A的后缀在前，那么 height 就是 B的后缀 与前面 A的后缀的最长相同长度
二、后缀排名中，A的后缀在前 B的后缀在后，那么 height 就是 A 的后缀与 前面 B 的后缀的最长相同长度
所以要扫两遍，分别处理这两种情况
针对第一种情况而言：
用一个单调栈维护 最小公共长度，同时要记录每个最小公共长度的状态（即当前这种最小公共长度是包含了多少个 A 前缀的了）
每一次遇到一个 B 的后缀就统计与前面的A的后缀能产生多少个长度不小于 K 的公共子串。
对于第二种情况处理的方法也是一样。
AC code：
/*
POJ 3415
给定两个字符串 A 和 B， 求长度不小于 K 的公共子串的个数，
常用技巧，通过在中间添加特殊标记符连接两个串，把两个串的问题转换为 一个串的问题
按照 height 分组。
这里有两种情况
一、后缀排名中， B的后缀在后 A的后缀在前，那么 height 就是 B的后缀 与前面 A的后缀的最长相同长度
二、后缀排名中，A的后缀在前 B的后缀在后，那么 height 就是 A 的后缀与 前面 B 的后缀的最长相同长度
所以要扫两遍，分别处理这两种情况
针对第一种情况而言：
用一个单调栈维护 最小公共长度，同时要记录每个最小公共长度的状态（即当前这种最小公共长度是包含了多少个 A 前缀的了）
每一次遇到一个 B 的后缀就统计与前面的A的后缀能产生多少个长度不小于 K 的公共子串。
对于第二种情况处理的方法也是一样。 */ #include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#define INF 0x3f3f3f3f
#define LL long long
#define rep(i, j, k) for(int i = j; i < k; i++)
#define inc(i, j, k) for(int i = 1; i <= k; i++)
using namespace std;
const int MAXN = 2e5+;
int sa[MAXN];
int t1[MAXN], t2[MAXN], c[MAXN];
int Rank[MAXN], height[MAXN]; //void Da(int s[], int n, int m)
//{
// int i, k, p, *x = t1, *y = t2;
// rep(s, 0, m) c[s] = 0;
// rep(t, 0, n) c[x[t] = s[t]]++;
// rep(s, 1, m) c[s]+=c[s-1];
// for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
// for(k = 1; k <= n; k <<=1){ //倍增
// p = 0;
// for(i = n-k; i < n; i++) y[p++] = i;
// for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i]-k;
// for(i = 0; i < m; i++) c[i] = 0;
// for(i = 0; i< n; i++) c[x[y[i]]]++;
// for(i = 1; i < m; i++) c[i]+=c[i-1];
// for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
// swap(x, y);
// p = 1; x[sa[0]] = 0;
// for(i = 1; i < n; i++)
// x[sa[i]] = y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i+k]]?p-1:p++;
// if(p >= n) break;
// m = p;
// }
//}
//
//void getHeight(int s[], int n)
//{
// int i, j, k = 0;
// for(i = 0; i <= n; i++) Rank[sa[i]] = i;
// for(i = 0; i < n; i++){
// if(k) k--;
// j = sa[Rank[i]-1];
// while(s[i+k] == s[j+k])k++;
// height[Rank[i]] = k;
// }
//} void Da(int s[],int n,int m)
{
int i,k,p,*x=t1,*y=t2;
for(i=;i<m;i++)c[i]=;
for(i=;i<n;i++)c[x[i]=s[i]]++;
for(i=;i<m;i++)c[i]+=c[i-];
for(i=n-;i>=;i--)sa[--c[x[i]]]=i;
for(k=;k<=n;k<<=)
{
p=;
for(i=n-k;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
for(i=;i<m;i++)c[i]=;
for(i=;i<n;i++)c[x[y[i]]]++;
for(i=;i<m;i++)c[i]+=c[i-];
for(i=n-;i>=;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=;x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=y[sa[i-]]==y[sa[i]]&&y[sa[i-]+k]==y[sa[i]+k]?p-:p++;
if(p>=n)break;
m=p;
}
} void getHeight(int s[],int n)
{
int i,j,k=;
for(i=;i<=n;i++)Rank[sa[i]]=i;
for(i=;i<n;i++)
{
if(k)k--;
j=sa[Rank[i]-];
while(s[i+k]==s[j+k])k++;
height[Rank[i]]=k;
}
} char str1[MAXN], str2[MAXN];
int r[MAXN];
int sta[MAXN], stb[MAXN]; int main()
{
int k;
int n;
int len1, len2;
while(~scanf("%d", &k) && k){
scanf("%s %s", &str1, &str2);
len1 = strlen(str1);
len2 = strlen(str2);
// cout << str1 << endl << str2 << endl;
n = len1+len2+;
for(int i = ; i < len1; i++) r[i]=str1[i];
r[len1] = ;
for(int i = ; i < len2; i++) r[i+len1+]=str2[i];
r[len1+len2+] = ;
Da(r, n+, );
getHeight(r, n);
// for(int i = 0; i <= n; i++) cout << r[i] << " " ;
// puts("");
LL ans = , ss = ;
int top = ;
for(int i = ; i <= n; i++){
if(height[i] < k){
top = ;
ss = ;
continue;
}
int cnt = ;
if(sa[i-] < len1){
cnt++;
ss+=height[i]-k+;
}
while(top > && height[i] <= sta[top-]){
top--;
ss-=stb[top]*(sta[top]-height[i]);
cnt+=stb[top];
}
sta[top] = height[i];
stb[top++] = cnt;
if(sa[i] > len1) ans+=ss;
}
// cout << ans << endl;
ss = ;top = ;
for(int i = ; i <= n; i++){
if(height[i] < k){
top = ;
ss = ;
continue;
}
int cnt = ;
if(sa[i-] > len1){
cnt++;
ss+=height[i]-k+;
}
while(top > && height[i] <= sta[top-]){
top--;
ss-=stb[top]*(sta[top]-height[i]);
cnt+=stb[top];
}
sta[top] = height[i];
stb[top++] = cnt;
// cout << ss << endl;
if(sa[i] < len1) ans+=ss;
}
printf("%lld\n", ans);
}
return ;
}