算法思想一：枚举

解题思路：

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

图解：

代码展示：

C++版本 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S1 string字符串 S1
     * @param S2 string字符串 S2
     * @return string字符串
     */
    string CycleString(string S1, string S2) {
        // write code here
        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首尾相接（S1+S1），组成的新串就包含了所有的循环同构串。
找到最大匹配的时候采用对字符串前缀做哈希处理的方法，只需要统计一下每个位置是否匹配成功，然后用前缀和进行记录，之后直接做差就能得到在每一个循环同构串中的出现次数了。
最后找到相同情况下的字典序最小，可以用哈希比较两个串的字典序大小，通过二分长度找到两个串的相同的前缀长度，比较第一个不同字母的字典序就可以

代码展示：

C++版本 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S1 string字符串 S1
     * @param S2 string字符串 S2
     * @return string字符串
     */
    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) {
        // write code here
        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 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 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的长度，最坏情况为每个都是最大都需要二分法找字典序最小

空间复杂度：辅助数组占用空间