[数据结构与算法]leetcode 面试题01.09字符串轮赚

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

开始打算遍历两个字符串， 越做越麻烦，后来看题解知道应该这么做：“ 首先判断两个字符串长度是否相等,再判断把两个s1连起来能不能包含s2”

package mianshi;

import java.util.Arrays;

/**
 * @ClassName IsFlipedString
 * @Description TODO
 * @Author Achilles
 * @DATE 2021/9/3 16:28
 * @Version 1.0
 */

public class IsFlipedString {
    public boolean isFlipedString(String s1, String s2) {
        if(s1 == null || s2 == null){
            return false;
        }
        if(s1.length() != s2.length()){
            return false;
        }

        String s = s1 + s1;

        int res = kmpIndex(s, s2);
        System.out.println(res);
        return res != -1;
    }

    private int kmpIndex(String s, String t){
        int[] next = getNext(t);
        int i = 0, j = 0;

        while (i < s.length() && j < t.length()){
            if(j == -1 || s.charAt(i)==t.charAt(j)){
                i++;
                j++;
            }
            else {
                j = next[j];
            }
        }
        if(j >= t.length()){
            return (i-t.length());
        }
        else {
            return -1;
        }
    }

    private int[] getNext(String s){
        int[] next = new int[s.length()];
        int j, k;
        j = 0; k = -1;
        next[0] = -1;
        //因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
        //所以最后一次经过while循环时j为t.length-2
        while (j < s.length()-1){
            if(k == -1 || s.charAt(j) == s.charAt(k)){
                j++; k++;

                if (s.charAt(j)!=s.charAt(k)) {
                    //这里的s.charAt(k)是s.charAt(j)处字符不匹配而会回溯到的字符
                    //为什么？因为没有这处if判断的话，此处代码是next[j]=k;
                    //next[j]不就是s.charAt(j)不匹配时应该回溯到的字符位置嘛
                    next[j] = k;
                }
                else {
                    next[j] = next[k];
                }
                //这一个代码含义是不是呼之欲出了？
                //此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
                //用较为粗鄙语言表诉：即字符不匹配时回溯两层后对应的字符下标
//                next[j] = k;
                //对应字符匹配情况下，s与t指向同步后移
                //通过字符串"aaaaab"求next数组过程想一下这一步的意义
                //printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
            }else{
                k = next[k];
                //我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
                //也表示该处字符不匹配时应该回溯到的字符的下标
                //这个值给k后又进行while循环判断，此时t.data[k]即指最长相等前缀后一个字符**
                //为什么要回退此处进行比较，我们往下接着看。其实原理和上面介绍的KMP原理差不多
                //printf("(2) k=%d\n",k);
            }
        }
        return next;
    }
    public static void main(String[] args) {
        String s1 = "waterbottle";
        String s2 = "erbottlewat";
        boolean res = new IsFlipedString().isFlipedString(s1, s2);
        System.out.println("Res is "+res);



        String s3 = "aaaaab";

        int[] next = new IsFlipedString().getNext(s3);
        System.out.println("Res is "+res);
    }
}

使用kmp来做, kmp:KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。

求next的方法：

优化next的原理：

kmp算法的学习来源是：
https://blog.csdn.net/weixin_46007276/article/details/104372119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163090574116780261967375%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=163090574116780261967375&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_alltop_positive~default-1-104372119.pc_search_ecpm_flag&utm_term=kmp&spm=1018.2226.3001.4187