本文共 2301 字，大约阅读时间需要 7 分钟。

求两个串长度至少为$k$的相同子串对。

对串$A$建立$SAM$,拿串$B$在串$A$上跑

若以$i$结尾的$B$子串在$SAM$上跑到的节点是$p$，此时最大匹配长度是$l$

若$l<k$,当然不需要统计答案

若$l>=k$

那么对于节点$p$包含的子串类来说,有$l-max(k,len[f{a}_p]+1)+1$个子串满足条件

这些子串出现过$siz[p]$次

但是这样我们只统计了节点$p$,$p$的祖先也应该被统计!!!

比如$p$的父节点有$len[f{a}_i]-max(k,len[f{a}_{f{a}_i}]+1)+1$个子串满足条件…

所以我们可以打个标记,最后按照拓扑序向上递推即可

#include 
   
    #include 
    
     #include 
     
      using namespace std;typedef long long ll;const int maxn = 2e5+10;ll siz[maxn],len[maxn],k,fa[maxn];int zi[maxn][54],ed=1,id=1;char a[maxn],b[maxn];void insert(int c){
   	int p = ed, np = ++id; ed = np;	len[np] = len[p]+1; siz[np] = 1;	for( ; p&&zi[p][c]==0;p=fa[p] )	zi[p][c] = np;	if( p==0 )	fa[np] = 1;	else	{
   		int q = zi[p][c];		if( len[q]==len[p]+1 )	fa[np] = q;		else		{
   			int nq = ++id;			memcpy( zi[nq],zi[q],sizeof zi[nq] );			fa[nq] = fa[q], len[nq] = len[p]+1;			fa[np] = fa[q] = nq;			for( ; p && zi[p][c]==q;p=fa[p] )	zi[p][c] = nq;		}	}}int c[maxn],rk[maxn];ll f[maxn];void chiken_sort(){
   	for(int i=1;i<=id;i++)	c[len[i]]++;	for(int i=1;i<=id;i++)	c[i] += c[i-1];	for(int i=id;i>=1;i--)	rk[c[len[i]]--] = i; 	for(int i=id;i>=1;i--)	siz[fa[rk[i]]] += siz[rk[i]];}void init(){
   	for(int i=0;i<=id;i++)	{
   			memset( zi[i],0,sizeof zi[i] );		f[i] = siz[i] = rk[i] = c[i] = len[i] = fa[i] = 0;	}	ed = id = 1;}int tran(char w){
   	if( w>='a'&&w<='z' )	return w-'a';	return w-'A'+26;}signed main(){
   	while( cin >> k&&k  )	{
   		scanf("%s%s",a+1,b+1 );		int len1 = strlen( a+1 ), len2 = strlen( b+1 ); 		for(int i=1;i<=len1;i++)	insert( tran(a[i]) );		chiken_sort();		ll ans = 0,p = 1, l = 0;		for(int i=1;i<=len2;i++)		{
   			int c = tran( b[i] );			if( zi[p][c] )	p = zi[p][c], l++;			else			{
   				while( zi[p][c]==0&&p )	p = fa[p];				if( p==0 )	p = 1, l = 0;				else	l = len[p]+1, p = zi[p][c];			}			if( l
      
       =k )	f[fa[p]]++;		}		for(int i=id;i>=1;i--)		{
   			int u = rk[i];			if( f[u]==0 )	continue;			f[fa[u]] += f[u];			if( len[u]-max(k,len[fa[u]]+1)+1>=0 )				ans += 1ll*siz[u]*f[u]*( len[u]-max(k,len[fa[u]]+1)+1 );		}		cout << ans << endl;		init();	}}
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114898445 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！