字符串匹配

前言：本文参考代码随想录，加上自己的小总结。
其中代码随想录的目录安排非常得当，题的难度逐渐递增，这也是我参考的一大依据。
但是，还是要有自己的思考总结，把他人的转化为自己的，才是真正的掌握。
这里展示的代码可能不是最优解，但是可以帮助理清其中的区别联系。
Java宝藏链接
我不搬运代码，只是记录重点
字符串反转
话接上回，开始字符串匹配。

代码随想录中字符串的目录安排如下：

这次来说说6，7。
通过实现str()我掌握了我大学数据结构没学会的KMP
要解决这两个题，需要知道next数组，next数组是KMP的灵魂，也是这两题的共同之处


1.为什么要用这样next数组
2.next数组的定义和计算
这里涉及到前缀表的一个东西，我们要理解两个概念，前缀和后缀。
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
然后我们以字符串“abaab”为例来计算

然后，要长度相等的前缀和后缀进行比较，可以得到：

为了统一将每个数字进行减一操作（也可以不减，参照代码随想录）
对应构建next数组代码：

public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i<s.length(); i++){
            while(j>=0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }

            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

懂了这个以后，再来看看求str()问题，str()问题求取是求第一次出现的位置
分两种：1.没有返回-1
2.有。在有的过程中可能需要回退操作求助next数组，结果就是模式串被完全匹配

 public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        int[] next = new int[needle.length()];
        
        //构建next数组
        getNext(next, needle);
        int j = -1;
        
        for(int i = 0; i<haystack.length();i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }
            //找到
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

重复的子字符串的问题就是是否可以寻找到最小重复单元
而最小重复单元由next数组得到
看图大家就明白了
然后我们以字符串“abababab”为例来计算

减一是为了统一，可以发现next数组最大值是6

根据代码计算得到

你在发现用字符串“abababab”的长度8 - Max(next数组值) = 最小重复单元的长度
也就是length % 最小重复单元的长度 == 0；
当然前提是Max(next数组值) 存在（next[len-1]+1，其中j的初始值是-1）

public boolean repeatedSubstringPattern(String s) {
        if (s.equals("")) return false;

        int len = s.length();
        //s += s;

        char[] chars = s.toCharArray();
        int[] next = new int[len];
        next[0] = -1;
        
        // 构造 next 数组过程，j从-1开始(空格)，i从1开始
        for (int i = 1, j = -1; i < len; i++) {
            // 匹配不成功，j回到前一位置 next 数组所对应的值
            while (j >= 0 && chars[i] != chars[j + 1]) j = next[j];
            // 匹配成功，j往后移
            if (chars[i] == chars[j + 1]) j++;
            // 更新 next 数组的值
            next[i] = j;
        }

        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len-1] != -1 && len % (len - next[len-1]-1) == 0) {
            return true;
        }
        return false;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

到此，字符串部分结束，欢迎交流。