【BZOJ4566】[Haoi2016]找相同字符

Description

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两

个子串中有一个位置不同。

Input

两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母

Output

输出一个整数表示答案

Sample Input

aabb

bbaa

Sample Output

10

题解：本题跟差异那道题很相似，理论上可以直接一遍sa搞定，但是我比较懒，直接求了3遍sa。

子串相同的方案数=后缀的相同前缀长度总和，两个串的相同后缀长度总和=两个串连一起的总和-两个串内部的长度和

具体做法请见

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=400010;int n,m,len1,len2;int r[maxn],ra[maxn],rb[maxn],st[maxn],sa[maxn],h[maxn],rank[maxn];int q[maxn],t,ls[maxn],rs[maxn];long long ans,sum;char s1[maxn],s2[maxn];void work(){    int i,j,k,*x=ra,*y=rb,p;    for(i=0;i
        
         =0;i--)  sa[--st[x[i]]]=i;    for(p=j=1;p
         
          <<=1,m=p)    {        for(p=0,i=n-j;i
          
           =j) y[p++]=sa[i]-j; for(i=0;i
           
            =0;i--) sa[--st[x[y[i]]]]=y[i]; for(swap(x,y),x[sa[0]]=0,i=p=1;i
            
             =h[i]) rs[q[t--]]=i; q[++t]=i; } t=0; for(i=n-1;i>=0;i--) { while(t&&h[q[t]]>h[i]) ls[q[t--]]=i; q[++t]=i; } for(i=1;i