题解 | #MagicString#

题目描述
牛妹有有两个字符串S1与S2，她想知道S2在S1中的哪一个循环同构串中的出现次数最多，如果有多个，请输出字典序最小的一个。
循环同构串的定义：不断地将si...sn的部分提前到s1...si−1之前,得到一个新的字符串，这些新的字符串称为循环同构串。
例：abcc的循环同构串为：abcc,bcca,ccab,cabc。

如果S2没有在S1的任意一个循环同构串中出现则返回IMPOSSIBLE否则返回字符串代表答案。

方法一：暴力解法

求解思路
对于本题求解循环同构串，我们自然想到将所有的情况进行枚举，并且用S2与枚举出来的字符串进行一一对比，这样即可求解出题目所要求的字符串。

图片说明

解题代码

const int N=200010;
int n,m;
char s[N],T[N],S[N];
int nex[N];
class Solution {
public:
    void gao()
    {   //求得next数组
        int j=0;
        m=strlen(T+1);
        for (int i=2; i<=m; i++)
        {
            while(j&&T[i]!=T[j+1]) j=nex[j];
            if(T[j+1]==T[i]) j++;
            nex[i]=j; // 更新nex数组
        }
    }
    int match()
    {
        int j=0,count=0;
        n=strlen(S+1);
        for(int i=1; i<=n; i++)
        {
            while(j&&T[j+1]!=S[i]) j=nex[j]; // 如果不相等，则用nex数组进行替换
            if (T[j+1]==S[i]) j++;
            if (j==m)
            {
                count++;
                j=nex[j];
            }
        }
        return count; // 返回匹配结果
    }
    string CycleString(string S1, string S2)
    {
        strcpy(s+1,S1.c_str());
        strcpy(T+1,S2.c_str());
        gao();
        int len=strlen(s+1);
        for(int i=1;i<=2*len;i++) s[i+len]=s[i];
        int mx=0;
        for(int st=1;st<=len;st++) 
        {
            for(int i=1;i<=len;i++) S[i]=s[st+i-1];
            mx=max(mx,match()); // 进行匹配操作
        }
        if(mx==0) // 没有找到对应的循环同构串
        {
            return "IMPOSSIBLE";
        }
        string myans="{";
        for(int st=1;st<=len;st++) 
        {
            string str="";
            for(int i=1;i<=len;i++) S[i]=s[st+i-1];//进行循环，判断找循环同构串
            str=S+1;
            if(mx==match())
            {
                if(myans>str) myans=str;
            }
        }
        return myans; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $图片说明$
空间复杂度：对S1进行枚举循环同构串，因此空间复杂度为 $O(N)$

方法二：哈希的思想求解

求解思路
对于处理循环同构串，我们可以发现只需要拓展一倍的长度就可以表示所有的循环同构串了，即字符串A拓展到字符串AA，然后我们用哈希的思想对字符串进行匹配，最后得到本问题的答案。

图片说明

解题代码

typedef long long ll;
typedef unsigned long long ull;
const int N=200010;
const ull sed = 233;
int n,m;
ull h[N],ha[N];
char s[N],t[N];
ull get(int l,int r)
{
    return ha[r]-ha[l-1]*h[r-l+1];
}
bool pd(int st1,int st2,int len)
{
    if(ha[st1+len-1]-ha[st1-1]*h[len]==ha[st2+len-1]-ha[st2-1]*h[len]) return 1; //判断从st1与st2开始的长度为len的hash值是否相同
    return 0;
}
bool cmp(int st1,int st2)
{   //比较st1与st2开始的长度为n的串的字典序大小
    if(s[st1]!=s[st2])
        return s[st1]<s[st2];
    int l=1,r=n;
    while(l<r)
    {   //二分最长相同长度
        int mid=l+r>>1;
        if(pd(st1,st2,mid)) l=mid+1;
        else r=mid;
    }
    if(!pd(st1,st2,l)) l--;
    if(l==n) return 1;
    return s[st1+l]<s[st2+l]; // 比较第一个不同的字典序大小
}
int sum[N],add[N];
class Solution {
public:
    string CycleString(string S1, string S2)
    {
        h[0]=1;
        for(int i=1;i<N;i++) h[i]=h[i-1]*sed;
        strcpy(s+1,S1.c_str());
        n=strlen(s+1);
        for(int i=1;i<=n;i++) s[i+n]=s[i];
        for(int i=1;i<=n*2;i++) ha[i]=ha[i-1]*sed+s[i];
        s[2*n+1]='\0';
        strcpy(t+1,S2.c_str());
        m=strlen(t+1);
        if(m>n) return "IMPOSSIBLE";
        ull val=0; // S2的hash值
        for(int i=1;i<=m;i++) val=val*sed+t[i];
        for(int i=1;i+m-1<=n*2;i++) // 前缀和统计匹配次数
            if(get(i,i+m-1)==val) sum[i]=sum[i-1]+1;
            else sum[i]=sum[i-1];
        int maxcount=0;
        vector<int>v; // 匹配次数最大的起点集合
        for(int i=1;i<=n;i++) // 最大匹配次数
            maxcount=max(maxcount,sum[i+n-m+1]-sum[i-1]);
        if(maxcount==0)
        {
            return "IMPOSSIBLE";
        }
        for(int i=1;i<=n;i++)
        {   //记录次数最大的起点集合
            if(sum[i+n-m+1]-sum[i-1]==maxcount)
            {
                v.push_back(i);
            }
        }
        int mn=v[0];
        for(auto i:v)
        {   //获取字典序最小的串
            if(!cmp(mn,i)) mn=i;
        }
        s[mn+n]='\0';
        string ss=s+mn;
        return ss; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：对于字符串进行扩充，因此空间复杂度为 $O(N)$