题解 | #MagicString#

题意整理

给定两个字符串S1和S2。
求S2在S1的哪一个循环同构串中出现次数最多。
如果有多个这样的同构串，输出字典序最小的那一个。

方法一（kmp）

1.解题思路

首先初始化计数数组。
通过kmp算法，获取S2在同构串中出现的次数。
记录最大的出现次数。
通过最大出现次数定位到同构串起点索引，找到字典序最小的那一个。

通过kmp算法计算模式串在主串中出现次数，可参考我在牛客的另一篇题解：kmp题解入口

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S1 string字符串 S1
     * @param S2 string字符串 S2
     * @return string字符串
     */
    public String CycleString (String S1, String S2) {
        //如果S2比S1长，S2不可能出现在S1的循环同构串中
        if(S1.length()<S2.length()) return "IMPOSSIBLE";

        int n=S1.length();
        int m=S2.length();
        //初始化计数数组
        int[] cnt=new int[n];
        //S1拷贝一份拼接在后面，用于获取循环同构串
        S1=S1+S1;
        int max=0;
        for(int i=0;i<n;i++){
            //通过kmp算法，获取S2在同构串中出现的次数
            cnt[i]=getCnt(S2,S1,i);
            max=Math.max(max,cnt[i]);
        }

        if(max==0) return "IMPOSSIBLE";
        String res="";
        //选择最大出现次数中，字典序最小的同构串
        for(int i=0;i<n;i++){
            if(cnt[i]==max){
                if(res.equals("")||res.compareTo(S1.substring(i,i+n))>0){
                    res=S1.substring(i,i+n);
                }
            }
        }
        return res;
    }

    //T是主串，S是模式串，计算S在T中出现次数（限制T的范围在start到start+n-1）
    private int getCnt(String S, String T,int start) {
        //特殊情况判断
        int m=S.length(),n=T.length()/2;
        if(m>n||n==0) return 0;

        //初始化计数，获取next数组
        int cnt=0;
        int[] next=getNext(S);

        //遍历主串和模式串
        for(int i=start,j=0;i<start+n;i++){
            //只要不相等，回退到next数组记录的下一位
            while(j>0&&T.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            if(T.charAt(i)==S.charAt(j)) j++;
            //如果j为m，说明完全匹配一次
            if(j==m){
                //计数加一，索引回退到next数组记录的下一位
                cnt++;
                j=next[j-1];
            }
        }
        return cnt;
    }

    //获取next数组
    private int[] getNext(String S){
        int m=S.length();
        int[] next=new int[m];
        for(int i=1,j=0;i<m;i++){
            //只要不相等，回退到next数组记录的下一位
            while(j>0&&S.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            //前缀索引后移
            if(S.charAt(i)==S.charAt(j)) j++;
            //确定应该回退到的下一个索引
            next[i]=j;
        }
        return next;
    }
}

3.复杂度分析

时间复杂度：假设S1的长度为n，S2的长度为m，kmp算法获取出现次数的时间复杂度是 $O(n+m)$ ，总共有n个同构串，所以最终的时间复杂度是 $O(n*(n+m))$ 。
空间复杂度：需要额外大小为n的cnt数组，kmp中需要额外大小为m的next数组，所以空间复杂度是 $O(n+m)$ 。

方法二（自定义哈希值）

1.解题思路

简要分析：由于所有的循环同构串都可以通过截取S1+S1中以某一下标为起点，长度为n（n是原S1串的长度）的子串获取，只要将字符串通过某种方式映射为哈希值，通过哈希值前缀和数组，就可以得到任意子串的对应哈希值，于是就可以找到与S2哈希值相等的长度为m的所有子串的起点，然后再构造一个记录匹配起点次数的前缀和数组，就可以得到S2在所有同构串中出现的次数，找到最大的出现次数。在所有最大的出现次数对应的同构串中，选择哈希值最小的，即是字典序最小的那个同构串。

基本步骤：

初始化hash数组和seed数组。
通过自定义的sed和哈希计算给hash数组和seed数组赋值。
计算S2在S1的循环同构串中出现的起点位置次数的前缀和，通过这个前缀和数组统计最多出现次数。
根据最多出现次数，找到对应的同构串，再通过哈希值得到字典序最小的同构串。

动图展示（哈希值计算）：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S1 string字符串 S1
     * @param S2 string字符串 S2
     * @return string字符串
     */

    //用于记录哈希值前缀和
    int[] hash;
    //记录每一位的种子值
    int[] seed;
    //设置种子值为26
    int sed=26;

    public String CycleString (String S1, String S2) {
        //如果S2比S1长，S2不可能出现在S1的循环同构串中
        if(S1.length()<S2.length()) return "IMPOSSIBLE";

        //初始化hash数组和seed数组
        int n=S1.length();
        hash=new int[2*n+1];
        seed=new int[2*n+1];

        S1=S1+S1;
        char[] arr=S1.toCharArray();
        seed[0]=1;
        //给hash数组和seed数组赋值
        for(int i=1;i<=2*n;i++){
            hash[i]=hash[i-1]*sed+arr[i-1]-'a';
            seed[i]=seed[i-1]*sed;
        }

        int m=S2.length();
        int hashOfS2=0;
        //计算S2的哈希值
        for(int i=1;i<=m;i++){
            hashOfS2=hashOfS2*sed+S2.charAt(i-1)-'a';
        }

        //用于记录S2在S1的循环同构串中出现的起点位置次数的前缀和
        int[] sum=new int[2*n+1];
        for(int i=1;i+m-1<=2*n;i++){
            if(hashOfS2==getHash(i,i+m-1)){
                sum[i]=sum[i-1]+1;
            }
            else{
                sum[i]=sum[i-1];
            }
        }

        //记录在循环同构串中出现的最多次数
        int maxCnt=0;
        for(int i=1;i<=n;i++){
            //起点为i终点为i+n的同构串，它最后一次可能匹配到S2的起点在i+n-(m-1)
            maxCnt=Math.max(maxCnt,sum[i+n-(m-1)]-sum[i-1]);
        }
        //如果为0，直接返回"IMPOSSIBLE"
        if(maxCnt==0) return "IMPOSSIBLE";

        //记录字典序最小同构串的起点位置
        int start=-1;
        for(int i=1;i<=n;i++){
            if(maxCnt==sum[i+n-(m-1)]-sum[i-1]){
                if(start==-1||getHash(start,start+m-1)>getHash(i,i+m-1)){
                    start=i;
                }
            }
        }
        //因为计算哈希值时，下标是从1开始的，这里要还原
        return S1.substring(start-1,start-1+n);
    }

    //计算起点为l，终点为r的字符串的哈希值
    private int getHash(int l,int r){
        //因为l-1在左边，是高位，要补齐到和r一样的长度
        return hash[r]-hash[l-1]*seed[r-l+1];
    }

}

3.复杂度分析

时间复杂度：假设S1的长度为n，S2的长度为m，所有的循环都是线性的，所以时间复杂度是 $O(n+m)$ 。
空间复杂度：需要额外大小为 $2*n+1$ 的hash数组、seed数组和sum数组，空间复杂度是 $O(n)$ 。