http://poj.org/problem?id=3415
题意：
求长度不小于K的公共子串的个数。
思路：
好题！！！拉丁字母让我Wa了好久！！单调栈又让我理解了好久！！太弱啊！！
最简单的就是暴力枚举，算出LCP，那么这个LCP对答案的贡献就是$x-k+1$。
我们可以将height进行分组，大于等于k的在同一组，如果两个后缀的最长公共子串>=k，那么它们肯定在同一个组内。现在从头开始扫，每遇到A的后缀时，就统计一下它和它前面的B的后缀能组成多少长度>=k的公共子串，然后再反过来处理B的后缀即可，一共需要扫两遍。但是这样的时间复杂度是O(n^2)，是行不通的。
因为两个后缀的LCP是它们之间的最小height值，所以可以维护一个自底向上递增的单调栈，如果有height值小于了当前栈顶的height值，那么大于它的那些只能按照当前这个小的值来计算。这样分别处理两次，一次处理A的后缀，一次处理B的后缀。需要记录好栈里的和以及每个组内的后缀数。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn=*1e5+; int n;
char s[maxn],s1[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn];
int Rank[maxn],height[maxn];
int sta[maxn],cnt[maxn]; void build_sa(int m)
{
int *x=t,*y=t2;
//基数排序
for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[i]=s[i]]++;
for(int i=;i<m;i++) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[i]]]=i;
for(int k=;k<=n;k<<=)
{
int p=;
//直接利用sa数组排序第二关键字
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
//基数排序第一关键字
for(int i=;i<m;i++) c[i]=;
for(int i=;i<n;i++) c[x[y[i]]]++;
for(int i=;i<m;i++) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];
//根据sa和y计算新的x数组
swap(x,y);
p=;
x[sa[]]=;
for(int 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 n)
{
int i,j,k=;
for(i=;i<=n;i++) Rank[sa[i]]=i;
for(i=;i<n;i++)
{
if(k) k--;
int j=sa[Rank[i]-];
while(s[i+k]==s[j+k]) k++;
height[Rank[i]]=k;
}
} int main()
{
int k;
//freopen("in.txt","r",stdin);
while(~scanf("%d",&k))
{
if(!k) break;
scanf("%s%s",s,s1);
int len1 = strlen(s);
int len2 = strlen(s1);
s[len1]='@';
for(int i=;i<len2;i++) s[len1++i]=s1[i];
s[len1+len2+]='*';
s[len1+len2+]='\0';
n=strlen(s);
build_sa();
getHeight(n-); ll sum=,ans=; //sum代表栈里对答案的贡献值，cnt数组记录的是一个组内的后缀数
int top=;
for(int i=;i<n;i++) //处理A和它前面的B的公共前缀
{
if(height[i]<k) {top=;sum=;continue;}
int num=;
while(top && sta[top]>height[i])
{
sum-=(ll)(sta[top]-k+)*cnt[top]; //在这儿比height[i]大的都要变成height[i]，所以先减去先前加上去的
sum+=(ll)(height[i]-k+)*cnt[top]; //乘cnt[top]的原因是可能有多个合并成一个了，比如4,5,3，那么4和5都只能以3来计算
num+=cnt[top]; //那么此时这三个可以合并在一起，cnt个数就是3，和就是3*3=9
top--;
}
sta[++top]=height[i];
if(sa[i-]>len1)
{
sum+=(ll)height[i]-k+;
cnt[top]=num+;
}
else cnt[top]=num;
if(sa[i]<len1)
ans+=sum;
} sum=,top=;
for(int i=;i<n;i++) //处理B和它前面的A的公共前缀
{
if(height[i]<k) {top=;sum=;continue;}
int num=;
while(top && sta[top]>height[i])
{
sum-=(ll)(sta[top]-k+)*cnt[top];
sum+=(ll)(height[i]-k+)*cnt[top];
num+=cnt[top];
top--;
}
sta[++top]=height[i];
if(sa[i-]<len1)
{
sum+=(ll)height[i]-k+;
cnt[top]=num+;
}
else cnt[top]=num;
if(sa[i]>len1)
ans+=sum;
}
printf("%I64d\n" , ans);
}
return ;
}