题解 | #MagicString#

思路：

题目的主要信息：

• 循环同构串：遍历字符串，每到一个字符的时候，将其及后面的字符接到最前面，公式为
• 要在S1的所有循环同构串中找到出现S2次数最多的一个，若相同次数则返回字典序最小
• 两个字符串只由小写字母构成

方法一：暴力法
具体做法：
遍历S1的每一个位置使用substr函数进行同构操作，每一个同构串我们在其中找到S2出现的次数，如果次数更多直接更新，如果次数相等则比较字典序后更新。

class Solution {
public:
    string CycleString(string S1, string S2) {
        string res = "";
        int maxnum = 0;
        if(S2.length() > S1.length())  //S2不能比S1长
            return "IMPOSSIBLE";
        for(int i = 1; i < S1.length(); i++){
            string temp = S1.substr(i) + S1.substr(0, i); //构造同构串
            int count = 0, begin = -1;
            while((begin = S1.find(S2, begin + 1)) != string::npos){ //寻找出现次数
                count++;
                begin = begin + S2.length();
            }
            if(count > maxnum){ //次数更大直接更新
                maxnum = count;
                res = temp;
            }else if(count == maxnum) //次数相等看字典序
                res = res < temp ? res : temp;
        }
        if(maxnum == 0) //没找到
            return "IMPOSSIBLE";
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历一次字符串，加上遍历字符串寻找出现次数
• 空间复杂度：，临时遍历temp存储同构串

方法二：哈希+二分
具体做法：
其实构造循环同构串不需要像方法一那样依次遍历，只需要将S1首尾相接，组成的新串就包含了所有的循环同构串。
找到最大匹配的时候我们采用对字符串前缀做哈希处理的方法，只需要统计一下每个位置是否匹配成功，然后用前缀和进行记录，之后直接做差就能得到在每一个循环同构串中的出现次数了。
最后找到相同情况下的字典序最小，可以用比较两个串的字典序大小，通过二分长度找到两个串的相同的前缀长度，比较他们第一个不同字母的字典序就可以了，这样比较采用了二分法，因此只需要

class Solution {
public:
    vector<int> h;
    vector<int> hash;//h数组存储sed的次方，ha存储的是前缀hash值
    string s, t; //s中为S1首尾相加，t为S2的全局变量
    int get(int l, int r) {//获取l到r的hash值
        return hash[r] - hash[l - 1] * h[r - l + 1];
    }
    bool judge(int str1, int str2, int len) {//判断从str1与str2开始的长度为len的hash值是否相同
        if(hash[str1 + len - 1] - hash[str1 - 1] * h[len] == hash[str2 + len - 1] - hash[str2 - 1] * h[len]) 
            return 1;
        return 0;
    }
    bool comp(int str1, int str2, int m, int n) {//比较st1与st2开始的长度为n的串的字典序大小
        if(s[str1] != s[str2]) 
            return s[str1] < s[str2];
        int l = 1, r = n;
        while(l < r) {//二分最长相同长度
            int mid = (l + r) / 2;
            if(judge(str1, str2, mid))
                l = mid + 1;
            else
                r = mid;
        }
        if(!judge(str1, str2, l)) 
            l--;
        if(l == n) 
            return 1;
        return s[str1 + l] < s[str2 + l];//比较第一个不同的字典序大小
    }
    string CycleString(string S1, string S2) {
        if(S2.length() > S1.length())  //S2不能比S1长
            return "IMPOSSIBLE";
        int n = S1.length();
        int m = S2.length();
        int sed = 27;
        h.resize(2 * n + 1);
        hash.resize(2 * n + 1);
        h[0] = 1;
        for(int i = 1; i < h.size(); i++) 
            h[i] = h[i - 1] * sed;
        s = " " + S1 + S1;  //S1字符串前后相加
        for(int i = 1; i <= 2 * n; i++) //S1的hash值
            hash[i] = hash[i - 1] * sed + s[i];
        t = " " + S2;
        vector<int> sum(2 * n + 1, 0);
        int 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 maxnum = 0;
        vector<int> start;//匹配次数最大的起点集合
        for(int i = 1; i <= n; i++)//最大匹配次数
            maxnum = max(maxnum, sum[i + n - m + 1] - sum[i - 1]);
        if(maxnum == 0) 
            return "IMPOSSIBLE";
        for(int i = 1; i <= n; i++) {//记录次数最大的起点集合
            if(sum[i + n - m + 1] - sum[i - 1] == maxnum)
                start.push_back(i);
        }
        int temp = start[0];
        for(int i = 1; i < start.size(); i++) //找到最小字典序
            if(!comp(temp, start[i], m, n))
                temp = start[i];
        return s.substr(temp, n); //截取n的长度
    }
};

复杂度分析：

• 时间复杂度：，n为S1的长度，最坏情况为每个都是最大都需要二分法找字典序最小
• 空间复杂度：，使用了多个辅助数组何辅助字符串