Magic String题解_牛客博客

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

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个循环同构串，对于每个循环同构串去 $O(|S1|*|S2|)$ 求得匹配次数，当然这个过程也可以用kmp优化到 $O(|S1|+|S2|)$ ，然后对于这多个匹配次数相同的串去 $O(|S1|)$ 的去比较字典序大小。时间复杂度 $O(|S1|^2*|S2|)$ 或者 $O((|S1|+|S2|)*|S1|)$ ,空间复杂度 $O(|S1|+|S2|)$ 。

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
其实这题还可以后缀数组做，只需要把第二个串拼接在第一个串后面，然后在 $height$ 数组中找到第二个串的出现位置 $pos$ ，并对之后所有与 $pos$ 的最长公共前缀的长度等于 $|S2|$ 的位置进行标记，从而统计最多的出现次数 $cnt$ 。最后再去 $height$ 数组从前往后找第一个出现次数为 $cnt$ 的位置就可以输出答案了。时间复杂度 $O(|S1|+|S2|)$ ,空间复杂度 $O(|S1|+|S2|)$ 。