Magic String题解

解法1：AC
首先来看循环同构串如何进行处理？发现其实只需要拓展一倍的长度就可以表示所有的循环同构串了。紧接着是如何确定最多的出现次数。这个我们一般会考虑进行处理，只需要统计一下每个位置是否匹配成功，然后用前缀和进行记录，之后直接做差就能得到在每一个循环同构串中的出现次数了。最后就是如何找到字典序最小了。可以用做到比较两个串的字典序大小。可以通过二分长度找到两个串的相同的前缀长度，比较他们第一个不同字母的字典序就可以了。时间复杂度,空间复杂度。

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];//h数组存储sed的次方，ha存储的是前缀hash值
char s[N],t[N];
ull get(int l,int r) {//获取[l,r]的hash值
    return ha[r]-ha[l-1]*h[r-l+1];
}
bool pd(int st1,int st2,int len) {//判断从st1与st2开始的长度为len的hash值是否相同
    if(ha[st1+len-1]-ha[st1-1]*h[len]==ha[st2+len-1]-ha[st2-1]*h[len]) return 1;
    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:
    /**
     * 
     * @param S1 string字符串 S1
     * @param S2 string字符串 S2
     * @return string字符串
     */
    string CycleString(string S1, string S2) {
        // write code here
        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 mxcnt=0;
        vector<int>v;//匹配次数最大的起点集合
        for(int i=1;i<=n;i++)//最大匹配次数
            mxcnt=max(mxcnt,sum[i+n-m+1]-sum[i-1]);
        if(mxcnt==0) {
            return "IMPOSSIBLE";
        }
        for(int i=1;i<=n;i++) {//记录次数最大的起点集合
            if(sum[i+n-m+1]-sum[i-1]==mxcnt) {
                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;
    }
};

解法2：TLE
枚举这n个循环同构串，对于每个循环同构串去求得匹配次数，当然这个过程也可以用kmp优化到，然后对于这多个匹配次数相同的串去的去比较字典序大小。时间复杂度或者,空间复杂度。

const int N=200010;
int n,m;
char s[N],T[N],S[N];
int nex[N];
class Solution {
public:
    /**
     * 
     * @param S1 string字符串 S1
     * @param S2 string字符串 S2
     * @return string字符串
     */
    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;
        }
    }
    int match() {//kmp匹配
        int j=0,cnt=0;
        n=strlen(S+1);
        for(int i=1; i<=n; i++) {
            while(j&&T[j+1]!=S[i]) j=nex[j];
            if (T[j+1]==S[i]) j++;
            if (j==m) {
                cnt++;
                j=nex[j];
            }
        }
        return cnt;
    }
    string CycleString(string S1, string S2) {
        // write code here
        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 ans="{";
        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(ans>str) ans=str;
            }
        }
        return ans;
    }
};

解法3：AC
其实这题还可以后缀数组做，只需要把第二个串拼接在第一个串后面，然后在数组中找到第二个串的出现位置，并对之后所有与的最长公共前缀的长度等于的位置进行标记，从而统计最多的出现次数。最后再去数组从前往后找第一个出现次数为的位置就可以输出答案了。时间复杂度,空间复杂度。