(题目链接)

题意

　　一个字符串求它有多少个形如AABB的子串。

Solution

　　其实跟后缀数组里面一个论文题处理方式差不多吧。

　　先处理出以位置${x}$为终点的${AA}$串的个数，区间加法用差分处理，然后处理出以位置${y}$为起点的${BB}$串的个数，统计答案。

细节

　　清空数组，后缀数组里面的${wa,wb}$数组也要清空。开LL

代码

// uoj219#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define inf 1ll<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;int sa[2][maxn],rank[2][maxn],height[2][maxn];int ST[2][maxn][30],Log[maxn],bin[30];char s[maxn];LL cnt[maxn];namespace Suffix { int wa[maxn],ww[maxn],wb[maxn]; bool cmp(int *r,int a,int b,int l) { return r[a]==r[b] && r[a+l]==r[b+l]; } void da(char *r,int *sa,int n,int m) { int i,j,p,*x=wa,*y=wb; for (i=0;i<=n+1;i++) wa[i]=wb[i]=0; //important for (i=0;i<=m;i++) ww[i]=0; for (i=1;i<=n;i++) ww[x[i]=r[i]]++; for (i=1;i<=m;i++) ww[i]+=ww[i-1]; for (i=n;i>=1;i--) sa[ww[x[i]]--]=i; for (j=1,p=0;p
            
             <<=1,m=p) { for (p=0,i=n-j+1;i<=n;i++) y[++p]=i; for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j; for (i=0;i<=m;i++) ww[i]=0; for (i=1;i<=n;i++) ww[x[y[i]]]++; for (i=1;i<=m;i++) ww[i]+=ww[i-1]; for (i=n;i>=1;i--) sa[ww[x[y[i]]]--]=y[i]; for (swap(x,y),x[sa[1]]=p=1,i=2;i<=n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p : ++p; } } void calheight(int x,char *s,int *sa,int n) { for (int i=1;i<=n;i++) rank[x][sa[i]]=i; for (int k=0,i=1;i<=n;i++) { if (k) k--; int j=sa[rank[x][i]-1]; while (s[i+k]==s[j+k]) k++; height[x][rank[x][i]]=k; } }}using namespace Suffix;int query(int k,int x,int y) { if (x>y) swap(x,y);x++; int l=Log[y-x+1]; return min(ST[k][x][l],ST[k][y-bin[l]+1][l]);}void Init() { memset(s,0,sizeof(s)); memset(sa,0,sizeof(sa)); memset(ST,0,sizeof(ST)); memset(cnt,0,sizeof(cnt)); memset(rank,0,sizeof(rank)); memset(height,0,sizeof(height));}int main() { bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1; for (int i=2;i
             
              >1]+1; int T;scanf("%d",&T); while (T--) { Init(); scanf("%s",s+1); int n=strlen(s+1);LL ans=0; da(s,sa[0],n,300); calheight(0,s,sa[0],n); for (int i=1;i<=n>>1;i++) swap(s[i],s[n-i+1]); da(s,sa[1],n,300); calheight(1,s,sa[1],n); for (int i=0;i<=1;i++) for (int j=1;j<=n;j++) ST[i][j][0]=height[i][j]; for (int k=0;k<=1;k++) for (int j=1;j<=20;j++) for (int i=1;bin[j]+i<=n+1;i++) ST[k][i][j]=min(ST[k][i][j-1],ST[k][i+bin[j-1]][j-1]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j+=i) { //计算以当前位置为终点AA有多少个 int nxt=min(query(0,rank[0][j-i],rank[0][j]),i); int pre=min(query(1,rank[1][n-(j-i)+1],rank[1][n-j+1]),i); if (nxt+pre>i) cnt[j-pre+i]++,cnt[j+nxt]--; } for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; for (int i=1;i<=n;i++) for (int j=1;j<=n-i;j+=i) { //计算以当前位置为起点BB有多少个 int nxt=min(query(0,rank[0][j],rank[0][j+i]),i); int pre=min(query(1,rank[1][n-j+1],rank[1][n-(j+i)+1]),i); if (nxt+pre>i) ans+=cnt[max(0,j+nxt-i-1)]-cnt[max(0,j-pre-1)]; } printf("%lld\n",ans); } return 0;}