题意：
给出两个串，问这两个串的所有的子串中（重复出现的，只要是位置不同就算两个子串），长度大于等于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; //新建立nqtot-=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;}
生气是拿别人做错的事来惩罚自己
