Common Substrings

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 13892		Accepted: 4669

Description

A substring of a string T is defined as:

 

T(

i, 

k)=

T_iT_i

₊₁...

T_i+k

_-1, 1≤

i≤

i+k-1≤|

T|.

 

Given two strings A, B and one integer K, we define S, a set of triples (i, j, k):

 

S = {(

i, 

j, 

k) | 

k≥

K, 

A(

i, 

k)=

B(

j, 

k)}.

 

You are to give the value of |S| for specific A, B and K.

Input

The input file contains several blocks of data. For each block, the first line contains one integer K, followed by two lines containing strings A and B, respectively. The input file is ended by K=0.

1 ≤ |A|, |B| ≤ 10⁵

1 ≤ K ≤ min{|A|, |B|}

Characters of A and B are all Latin letters.

 

Output

For each case, output an integer |S|.

Sample Input

2aababaaabaabaa1xxxx0

Sample Output

225

Source

 题意： 求出长度不小于k的公共子串对数

 

通过height数组分组，某个组内的height都是大于等于k的，也就是任意两个后缀的最长公共前缀都至少为k。

扫描一遍，遇到一个B的后缀就与之前的A后缀进行统计，求出所有的满足的组数。但是这样的做法便是n^2的。

可以发现两个后缀的最长公共前缀为这一段的height值的最小值。

可以通过一个单调栈来维护一下，当前要入栈元素如果小于栈底元素，说明之后加入的B后缀与栈底的最长公共前缀是小于等于入栈的。这样就保证了单调栈内的height值是绝对递增的，逐渐合并，均摊可以达到o(n)的复杂度。

然后扫描两遍即可

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
              6   7 using namespace std;    8 int const N=200000+10;    9 int r[N],rk[N],wa[N<<1],wb[N<<1],num[N],h[N],K,sa[N],wv[N],id[N];  10 char s[N],s1[N];   11 int st[N][2];   12 long long ans;  13 int cmp(int *r,int x,int y,int z){ 14     return r[x]==r[y] && r[x+z]==r[y+z];   15 }  16 void build_sa(char  *r,int *sa,int n,int m){ 17     int i,j,p,*x=wa,*y=wb;   18     for(i=0;i
           
            =0;i--) sa[--num[x[i]]]=i; 22 for(j=1,p=1;p
            
             <<=1,m=p){ 23 for(p=0,i=n-j;i
             
              =j) y[p++]=sa[i]-j; 25 for(i=0;i
              
               =0;i--) sa[--num[wv[i]]]=y[i]; 30 swap(x,y); 31 for(p=1,i=1,x[sa[0]]=0; i
               
                =h[i]){ 52 sum-=st[top][1]*(st[top][0]-h[i]); 53 num+=st[top][1]; top--; 54 } 55 top++;st[top][0]=h[i]; st[top][1]=num; 56 if(id[sa[i]]==2) ans+=sum; 57 } 58 top=sum=0; 59 for(int i=s;i<=t;i++){ 60 int num=0; 61 if(id[sa[i-1]]==2) num++,sum+=h[i]-K+1; 62 while (top && st[top][0]>=h[i]){ 63 sum-=st[top][1]*(st[top][0]-h[i]); 64 num+=st[top][1]; top--; 65 } 66 top++; st[top][0]=h[i]; st[top][1]=num; 67 if(id[sa[i]]==1) ans+=sum; 68 } 69 } 70 void solve(int n){ 71 int t=0; 72 ans=0; 73 for(int i=1;i<=n;i++){ 74 if(h[i]>=K) { 75 if(!t) t=i; 76 }else if(t){ 77 calc(n,t,i-1); 78 t=0; 79 } 80 } 81 if(t) calc(n,t,n); 82 } 83 int main(){ 84 while (scanf("%d",&K)!=EOF && K){ 85 memset(s,0,sizeof(s)); 86 memset(id,0,sizeof(id)); 87 memset(h,0,sizeof(h)); 88 memset(rk,0,sizeof(rk)); 89 memset(sa,0,sizeof(sa)); 90 scanf("%s",s); 91 scanf("%s",s1); 92 int len=strlen(s); 93 s[len]=123; 94 strcat(s,s1); 95 len=strlen(s); 96 for(int i=0;s[i];i++) id[i]=2; 97 for(int i=0;s[i]!=123;i++) id[i]=1; 98 build_sa(s,sa,len+1,124); 99 build_h(s,sa,len); 100 solve(len); 101 cout<
                
                 <