ac(借助KMP)

如果一个字符串为str，把字符串的前面任意部分挪到后面形成的字符串交str的旋转词。比如str=“12345”，str的旋转串有“12345”、“45123”等等。给定两个字符串，判断是否为旋转词。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s1 = sc.next();
        String s2 = sc.next();
        if(isSame(s1, s2) && isTransform(s1, s2)){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    }

    static boolean isTransform(String s1, String s2){
        String s22 = s2 + s2;
        // s22 如果包含 s1 则是变形词
        return isMatch(s22, s1);
    }

    /**
     * KMP 字符串匹配
     */
    static boolean isMatch(String s1, String s2){
        char[] ss = s1.toCharArray();
        char[] ms = s2.toCharArray();
        int n = s1.length();
        int m = s2.length();

        int[] next = getNext(ms, m);
        int si = 0;
        int mi = 0;
        boolean flag = false;
        while (si < n){
            if(ss[si] == ms[mi]){
                si ++;
                mi ++;
            }else if(next[mi] == -1){
                si ++;
            }else {
                // 不匹配了 mi 直接等于 next[mi]
                mi = next[mi];
            }
            if(mi == m){
//                System.out.print((si-mi)+" ");
                flag = true;
                mi = 0;
            }
        }
//        if(mi != m && !flag) {
//            return false;
//        }
        return flag;
    }

    static int[] getNext(char[] p, int len) {
        int[] next = new int[len];

        next[0] = -1;
        if(len == 1){
            return next;
        }
        next[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos < len){
            if(p[pos-1] == p[cn]){
                next[pos++] = ++cn;
            }else if(cn > 0){
                cn = next[cn];
            }else {
                next[pos++] = 0;
            }
        }
        return next;
    }

    /**
     * 是否包含同样的字符，且每个字符数量相等
     */
    static boolean isSame(String s1, String s2){
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        int[] charCnt1 = new int[256];
        int[] charCnt2 = new int[256];

        for(int i=0;i<s1.length();i++){
            charCnt1[s1.charAt(i)] ++;
        }
        for(int i=0;i<s2.length();i++){
            charCnt2[s2.charAt(i)] ++;
        }
        boolean flag = true;
        for(int i=0;i<256;i++){
            if(charCnt1[i] != charCnt2[i]){
                flag = false;
                break;
            }
        }
        if(!flag){
            return false;
        }else {
            return true;
        }
    }

}
/*
4 4
abcd
cdab

YES


2 3
aa
aaa

NO
 */