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