给出两个串，问这两个串的所有的子串中（重复出现的，只要是位置不同就算两个子串），长度大于等于k的公共子串有多少个。
设A串构造SAM,B串去匹配A串
状态再添加一个值：sum,指这个状态出现多少次了。也就是说B串里面有多少个子串可以进入这个状态。
逆拓扑排序更新父亲结点。
匹配过程中：
注意一点，匹配过程中进入某个状态的串的长度是不固定的。
每次匹配长度lcs>=n时，当前状态符合条件的子串的数量为：(lcs-max(n,p->f->len+1)+1)，这个数量是不固定的。这个状态出现的次数为 p->right 。
如果p->f->len>=n，父亲状态是有符合状态的子串，而且符合状态的子串的数量是固定的。
先把这部分不固定的子串数量在匹配的过程中直接处理了。ans+=(lcs-max(n,p->f->len+1)+1)*p->right; 此时父亲状态出现的次数加一，p->f->sum++;
对于父亲状态，由于符合状态的子串的数量是固定的，所以可以先把这个状态出现的次数先求出来，等待匹配结束后再处理。
逆拓扑排序更新父亲结点的出现次数
对于每个结点>=n的状态
ans+=sam.pool[i].sum*sam.pool[i].right*(sam.pool[i].len-max(n,sam.pool[i].f->len+1)+1);
//出现次数*right集合大小*符合条件的子串数量
//len表示该状态可以接受的最长的字符串长度，即max,
//那么该状态可以接受的最短的字符串长度为p->f->len+1
//子串储存在状态里当且仅当字符串S,ST(S)！=NULL,S才为子串
//SAM 中的每个状态能够表示的不同子串的个数为 val - 父结点的 val
//所以在每增加一个点，或者说每次新建一个子父关系的时候，累加该状态所产生的子串数量
//求子串出现的数量等于求所在状态的right的集合大小，暂时还不会
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <string.h>
using namespace std;
const int maxn=100100;
struct suffixautomaton
{
struct node
{
long long len;//到这个状态允许的最大长长度，即max(s)
long long right;//这个状态在这个串里有几个位置，即right集合的大小
long long sum;
node *f,*ch[60]; //
node(){}
node(int l)
{
len=l;
f=NULL;
right=0;
sum=0;
memset(ch,0,sizeof(ch));
}
int calc() //返回该状态包含的子串数量
{
if(f==NULL)return 0;//
return len-(f->len);
}
};
node *root,*last;
node pool[maxn*2]; //储蓄结点用的
int cnt; //结点的数量
int tot; //当前sam可以表示的不同子串的数量，当建立子-父结点是，计算一次可以表示多少个子串
//当更改子-父关系时，必须先减去之前的状态所表示子串数量
void init()
{
root=last=pool;
memset(root,0,sizeof(node));
cnt=1;
tot=0;
}
node * new_node(int l=0)
{
node *x=pool+cnt++;
memset(x,0,sizeof(node));
if(l!=0) x->len=l;
return x;
}
void add(char ch)
{
int c=ch-'A';
node *p=last,*np=new_node(last->len+1);
while(p&&!p->ch[c])
p->ch[c]=np,p=p->f;
if(NULL==p)
{
np->f=root; //建立子父关系
tot+=np->calc(); //计算增加的子串。下同
}
else
{
if(p->ch[c]->len==p->len+1)
{
np->f=p->ch[c];
tot+=np->calc();
}
else
{
node *q=p->ch[c],*nq=new_node();
*nq=*q; //nq也建立了子父关系，nq->f=q->f;
nq->len=p->len+1; //新建立nq
tot-=q->calc(); //q点要更换子父关系，先减去
q->f=np->f=nq;
tot+=q->calc()+nq->calc()+np->calc(); //此处新建三个子父关系
while(p&&p->ch[c]==q)
p->ch[c]=nq,p=p->f;
}
}
last=np;
}
int bus[maxn*2]; //处理
int sorted[maxn*2]; //0--（cnt-1）为拓扑排序的出序顺序
void findr(char str[]) //处理某状态的right集合的大小，如果想要找到位置，node必须有东西标志位置
{
int l=strlen(str);
memset(bus,0,sizeof(bus));
for(int i=0;i<cnt;i++) bus[pool[i].len]++;
for(int i=1;i<=l;i++) bus[i]+=bus[i-1]; //
for(int i=0;i<cnt;i++) sorted[--bus[pool[i].len]]=i; //
node *p=root;
for(int i=0;i<l;i++) (p=p->ch[str[i]-'A'])->right++;
for(int i=cnt-1;i>0;i--)
if(pool[sorted[i]].f)
pool[sorted[i]].f->right+=pool[sorted[i]].right;
root->right=0; //还原
}
void solve() //求sum
{
node *p=root;
for(int i=cnt-1;i>0;i--)
if(pool[sorted[i]].f)
pool[sorted[i]].f->sum+=pool[sorted[i]].sum;
root->sum=0;
}
};
suffixautomaton sam;
char str[maxn];
char str2[maxn];
int main()
{
long long n;
while(scanf("%lld",&n),n)
{
scanf("%s",str);
sam.init();
int len=strlen(str);
for(int i=0;i<len;i++)
sam.add(str[i]);
sam.findr(str);
scanf("%s",str2);
int l=strlen(str2);
long long lcs=0;
long long ans=0;
suffixautomaton::node *p=sam.root;
for(int i=0;i<l;i++)
{
int c=str2[i]-'A';
if(p->ch[c])
p=p->ch[c],lcs++;
else
{
while(p&&!p->ch[c]) p=p->f;
if(p==NULL) p=sam.root,lcs=0;
else lcs=p->len+1,p=p->ch[c];
}
if(lcs>=n)
{
ans+=(lcs-max(n,p->f->len+1)+1)*p->right; //由于其的不固定性。直接处理了
p->f->sum++;//父亲出现次数加一
}
}
sam.solve();
for(int i=0;i<sam.cnt;i++)
{
if(sam.pool[i].len>=n) //对于符合的点，
ans+=sam.pool[i].sum*sam.pool[i].right*(sam.pool[i].len-max(n,sam.pool[i].f->len+1)+1);
}
printf("%lld\n",ans);
}
return 0;
}
原文：http://blog.csdn.net/u012915516/article/details/44656125