牛客网多校第一场-I题：Substring（SA求不同字串个数），牛客substring

牛客网多校第一场-I题：Substring（SA求不同字串个数），牛客substring

 

其实目前还不是很明白，先记录一下。

 

题目大意：

给你一个只含abc的字符串，求出所有不同构的子串。

同构的定义是指在所有的映射方案下不相同，例如abc可以映射为acb bac bca cab cba，这六个串是相互同构的。

 

解题思路：

题解做法，首先把abc的所有的映射方案枚举出来，枚举出来之后按照每种映射方案把S串变换为6个串。最后求出6个串的（不同字串数量+3*单一字符的串数量）/6。

首先看为什么要除6，假设我们原先字符串中含有ab这个子串，那么我们在处理这个串子串的时候必然会将它处理出来，其次在另外5个串中必然处理出ac ba bc ca cb这5个串，这些串我们会发现其实他们都是同构的，所以他们的结果需要除6.

其次对于单一字符的串 例如 aaa，它会被六种映射转为 aaa bbb bbb ccc ccc，我们对他们求子串（假定是长度为3的子串），就算我们有6个串其实也只能求出aaa bbb ccc这三个子串，所以单个字符的子串只被重复算了三次。

而我们能求出的所有单个字符的子串就是原串中最长连续相同字符的串的长度。

所以由此我们就可以推出上述的答案。

然而菜如我根本不知道把串连接起来每个串的不同的子串怎么算。或者可能是我理解的有点问题。希望大佬解惑。。。

 

Ac代码：

#include<bits/stdc++.h>
#define rank ra
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
const int INF=1e9+7;
char s[maxn];
int n,t1[maxn],t2[maxn],c[maxn],r[maxn];
int rank[maxn],height[maxn],sa[maxn];
bool cmp(int *r,int x,int y,int l)
{
    return r[x]==r[y]&&r[x+l]==r[y+l];
}
void da(int str[],int sa[],int rank[],int height[],int n,int m)
{
    n++;
    int i,j,*x=t1,*y=t2,p;
    for(int i=0;i<m;i++) c[i]=0;
    for(int i=0;i<n;i++) c[x[i]=str[i]]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int j=1;j<=n;j <<= 1)
    {
        p=0;
        for(int i=n-j;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(int i=0;i<=m;i++) c[i]=0;
        for(int i=0;i<n;i++) c[x[y[i]]]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(int i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)? p-1:p++;
        if(p>=n) break;
        m=p;
    }
    int k=0;
    n--;
    for(int i=0;i<=n;i++) rank[sa[i]]=i;
    for(int i=0;i<n;i++)
    {
        if(k) k--;
        j=sa[rank[i]-1];
        while(str[i+k]==str[j+k]) k++;
        height[rank[i]]=k;
    }
}
int main()
{
    while(scanf(" %d",&n)!=EOF)
    {
        scanf(" %s",s);
        int ls=strlen(s);
        int len=0;
        int per[3]={1,2,3}; //枚举所有映射
        do
        {
            for(int i=0;i<ls;i++)
                r[len++]=per[s[i]-'a'];
            r[len++]=0; //这里我猜测是为了把每个串区分开
        } while (next_permutation(per,per+3));
        len--;
        da(r,sa,rank,height,len,128);   //求sa和height
        ll res=0;
        for(int i=6;i<=len;i++)
        {
            ll left=n-sa[i]%(n+1);  //这一步不懂 这是实现求单个串的不同子串数量嘛?
            res+=max(0ll,left-height[i]);
        }
        ll ma=1,tt=0;
        for(int i=1;i<n;i++)    //求出单字符的子串数量
        {
            if(s[i]==s[i-1]) tt++;
            else tt=1;
            ma=max(ma,tt);
        }
        printf("%lld\n",(res+3*ma)/6);
    }
}