如题目所言

恳请大佬赐教。。。

题目描述

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

输入输出格式

输入格式：

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

输出格式：

输出一个整数表示答案

输入输出样例

输入样例#1：

aabb

bbaa

输出样例#1：

10

不会后缀自动机，所以后缀数组搞：

把两个串用一个很大的字符连接起来，求一个后缀数组。

考虑怎样暴力的算答案。

在rak数组中从前往后枚举起点，对于每个枚举的起点，

都暴力的往后扫，扫的过程中维护一个hei的最小值。

每到一个点的时候，如果这个点跟起点不属于一个串，

就将答案加上当前的最小值，这样是O(n2)的

考虑这个还能怎么算。

可以发现我们是维护hei的最小值。

那么我们要将hei排序，a[i]记录的就是排第i位的hei的编号

编号为0的后缀没有什么贡献，所以我们直接continue

处理每一个后缀时，我们凭借hei从大向小扫，

而每个hei[i]都与hei[i-1]有关

毕竟hei数组是按照sa数组中的排序计算的。。。

hei[i]与hei[i-1]对应的数组一定最相像

这样每次需要用的就是当前的hei。

扫的过程中用并查集维护一下每个串分别对哪些串有贡献的

（也就是hei数组的贡献）。

用乘法原理算一下当前的hei会有多少贡献。

就是用当前的hei乘上这个串和上一个串分别对

于两个不同的原串的乘积的和。 //注意：不同的！！！

这里写代码片#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long longusing namespace std;const int N=400100;int s[N];char s1[N];int cc[N],hei[N],rak[N],len,sa[N],a[N],b[N],l;int fa[N],st[N],ed[N]; int cmp2(const int &a,const int &b){    return hei[a]>hei[b];}int cmp(int *y,int a,int b,int k){    int ra1=y[a];    int rb1=y[b];    int ra2=a+k>=len ? -1:y[a+k];    int rb2=b+k>=len ? -1:y[b+k];    return ra1==rb1&&ra2==rb2;}void make_sa(){    int i,k,m,p;    m=28;  //最大到27     int *t,*x=a,*y=b;    for (i=0;i
          
           =0;i--) sa[--cc[x[i]]]=i; for (k=1;k<=len;k<<=1) { p=0; for (i=len-k;i
           
            =k) y[p++]=sa[i]-k; for (i=0;i
            
             =0;i--) sa[--cc[x[y[i]]]]=y[i]; t=x;x=y;y=t; x[sa[0]]=0; p=1; for (i=0;i
             
              =len) break; m=p; } return;}void make_hei(){ int i,k=0; for (i=0;i