脚本宝典收集整理的这篇文章主要介绍了力扣28题、459题(KMP算法),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
KMP算法
要在文本串:aabaabaafa 中查找是否出现过一个模式串:aabaaf。
本题用-1的方式实现
前缀表是下标i之前(包括i)的字符串,有多大长度的相同前缀后缀
next[i]表示i(包括i)之前最长相等的前后缀长度 - 1(其实就是j)
class Solution { 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; } } public int strStr(String haystack, String needle) { if (needle.length() == 0){ return 0; } int[] next = new int[needle.length()]; 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的方式实现
最长相等前后缀的长度为:next[len - 1] + 1
数组长度为len
如果len % (len - (next[len - 1] + 1)) == 0 ,
则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除,说明有该字符串有重复的子字符串。
(数组长度-最长相等前后缀的长度) 相当于第一个周期的长度,也就是一个周期的长度
如果这个周期可以被整除,就说明整个数组就是这个周期的循环
class Solution { 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; } } public boolean rePEatedSubstringPattern(String s) { if (s.length() == 0){ return false; } int[] next = new int[s.length()]; getNext(next, s); int len = s.length(); if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) { return true; } return false; } }
以上是脚本宝典为你收集整理的力扣28题、459题(KMP算法)全部内容,希望文章能够帮你解决力扣28题、459题(KMP算法)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。