kmp算法理论基础知识
核心思想
利用已经部分匹配的结果而加快模式串的滑动速度！
且主串S的指针i不必回溯！相较于BF算法的O(N * M)，KMP算法时间复杂度可提速到O(N + M)!
用处
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
例如:
BF算法
KMP
可以看出，如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
什么是前缀表？
next数组就是一个前缀表（prefix table）。
前缀表有什么作用呢？
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
前缀表是啥？
记录在模式串中下标i之前（包括i）的字符串中，每个位置的最长相等前后缀。
最长相等前后缀的概念是啥？
字符串的前缀：是指不包含最后一个字符的所有以第一个字符开头的连续子串；
后缀：是指不包含第一个字符的所有以最后一个字符结尾的连续子串；
前缀表要求的就是相同前后缀的长度，此时就要问了前缀表是如何记录的呢？
为什么一定要用前缀表
前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。
前缀表与next数组
很多KMP算法的时间都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？
next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。
构建next数组
next数组代码图解
28. 实现 strStr()
题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
题目
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
思路
使用kmp算法解决。
代码
1 class Solution {
2 /**
3 * 基于窗口滑动的算法
4 * <p>
5 * 时间复杂度：O(m*n)
6 * 空间复杂度：O(1)
7 * 注：n为haystack的长度，m为needle的长度
8 */
9 public int strStr(String haystack, String needle) {
10 int m = needle.length();
11 // 当 needle 是空字符串时我们应当返回 0
12 if (m == 0) {
13 return 0;
14 }
15 int n = haystack.length();
16 if (n < m) {
17 return -1;
18 }
19 int i = 0;
20 int j = 0;
21 while (i < n - m + 1) {
22 // 找到首字母相等
23 while (i < n && haystack.charAt(i) != needle.charAt(j)) {
24 i++;
25 }
26 if (i == n) {// 没有首字母相等的
27 return -1;
28 }
29 // 遍历后续字符，判断是否相等
30 i++;
31 j++;
32 while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
33 i++;
34 j++;
35 }
36 if (j == m) {// 找到
37 return i - j;
38 } else {// 未找到
39 i -= j - 1;
40 j = 0;
41 }
42 }
43 return -1;
44 }
45 }
1 // 方法一
2 class Solution {
3 public void getNext(int[] next, String s){
4 int j = -1;
5 next[0] = j;
6 for (int i = 1; i < s.length(); i++){
7 while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
8 j=next[j];
9 }
10
11 if(s.charAt(i) == s.charAt(j+1)){
12 j++;
13 }
14 next[i] = j;
15 }
16 }
17 public int strStr(String haystack, String needle) {
18 if(needle.length()==0){
19 return 0;
20 }
21
22 int[] next = new int[needle.length()];
23 getNext(next, needle);
24 int j = -1;
25 for(int i = 0; i < haystack.length(); i++){
26 while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
27 j = next[j];
28 }
29 if(haystack.charAt(i) == needle.charAt(j+1)){
30 j++;
31 }
32 if(j == needle.length()-1){
33 return (i-needle.length()+1);
34 }
35 }
36
37 return -1;
38 }
39 }
1 class Solution {
2 //前缀表（不减一）Java实现
3 public int strStr(String haystack, String needle) {
4 if (needle.length() == 0) return 0;
5 int[] next = new int[needle.length()];
6 getNext(next, needle);
7
8 int j = 0;
9 for (int i = 0; i < haystack.length(); i++) {
10 while (j > 0 && needle.charAt(j) != haystack.charAt(i))
11 j = next[j - 1];
12 if (needle.charAt(j) == haystack.charAt(i))
13 j++;
14 if (j == needle.length())
15 return i - needle.length() + 1;
16 }
17 return -1;
18
19 }
20
21 private void getNext(int[] next, String s) {
22 int j = 0;
23 next[0] = 0;
24 for (int i = 1; i < s.length(); i++) {
25 while (j > 0 && s.charAt(j) != s.charAt(i))
26 j = next[j - 1];
27 if (s.charAt(j) == s.charAt(i))
28 j++;
29 next[i] = j;
30 }
31 }
32 }
1 class Solution {
2 public int strStr(String haystack, String needle) {
3 if(needle.length() ==0)
4 return 0;
5 // char[] chars1 = haystack.toCharArray();
6 // char[] chars2 = needle.toCharArray();
7 //kmp算法
8 int[] next = getNext(needle);
9 int i = 0,j = 0;
10 while(i < haystack.length() && j < needle.length()){
11 if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
12 i++;
13 j++;
14 }else{
15 j = next[j];
16 }
17 if(j == needle.length())
18 return i - needle.length();
19 }
20
21 return -1;
22 }
23 public int[] getNext(String s) {
24 int[] next = new int[s.length()];
25 next[0] = -1;
26 int j = 0, k =-1;
27 while(j < s.length() -1) {
28 if(k == -1 || s.charAt(j) == s.charAt(k) ){
29
30 k++;
31 j++;
32 next[j] = k;
33
34 }
35 else
36 k = next[k];
37 }
38 return next;
39 }
40 }
459.重复的子字符串
题目链接：459. 重复的子字符串 - 力扣（LeetCode）
题目
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
思路
暴力法：一个for循环获取 子串的终止位置， 然后判断子串是否能重复构成字符串即可，时间复杂度O（n^2）。
移动匹配：当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：
也就是由前后相同的子串组成。
那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前后的子串做后串，就一定还能组成一个s，如图：
所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
KMP算法：
首先回顾下前后缀的定义。
- 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
- 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串；
在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里拿字符串s：abababab 来举例，ab就是最小重复单位，如图所示：
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除 （len % (len - (next[len - 1] + 1)) == 0），
就说明整个数组就是这个周期的循环。
具体推理过程可看：代码随想录 (programmercarl.com)
代码
1 // 暴力法
2 class Solution {
3 public boolean repeatedSubstringPattern(String s){
4 //假设子字符串长度为 n，不断用第一个子字符串和后面的子字符串比较，比较次数就是 s的长度
5 int num = 0;
6
7 //用来选择 子字符串的 长度，因为 s 由子字符串组成，子字符串一定比 s 的一半小
8 for(int i = 0; i < s.length()/2; i++){
9
10 //如果 s 长度不是 子字符串的 倍数
11 if(s.length()%(i+1) != 0) continue;
12
13 //依次对子字符串的每个字符与后面各个字符串对应位置比较
14 for(int j=0; j<i+1; j++){
15 for(int k=j; k<s.length(); k=k+i+1){
16 if(s.charAt(j) != s.charAt(k)){
17 num = 0;
18 break;
19 }
20 else num++;
21 }
22 }
23 //代表我们比较成功的次数与 s 相等
24 if( num== s.length()) return true;
25 }
26 return false;
27 }
28 }
1 // 移动匹配
2 class Solution {
3 public boolean repeatedSubstringPattern(String s){
4 String t = s + s;
5 t = t.substring(1,t.length() - 1);
6 return t.contains(s);
7 }
8 }
1 // KMP算法
2 class Solution {
3 public boolean repeatedSubstringPattern(String s) {
4 if (s.equals("")) return false;
5
6 int len = s.length();
7 // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
8 s = " " + s;
9 char[] chars = s.toCharArray();
10 int[] next = new int[len + 1];
11
12 // 构造 next 数组过程，j从0开始(空格)，i从2开始
13 for (int i = 2, j = 0; i <= len; i++) {
14 // 匹配不成功，j回到前一位置 next 数组所对应的值
15 while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
16 // 匹配成功，j往后移
17 if (chars[i] == chars[j + 1]) j++;
18 // 更新 next 数组的值
19 next[i] = j;
20 }
21
22 // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
23 if (next[len] > 0 && len % (len - next[len]) == 0) {
24 return true;
25 }
26 return false;
27 }
28 }
标签：459,charAt,int,needle,随想录,length,next,算法,字符串 From： https://www.cnblogs.com/xpp3/p/17115151.html