28.strStr()
基本思想:
KMP算法
具体实现:
要在文本串:aabaabaafa 中查找是否出现过一个模式串:aabaaf。
A 计算前缀表,得到next数组
本题用-1的方式实现
前缀表是下标i之前(包括i)的字符串,有多大长度的相同前缀后缀
next[i]表示i(包括i)之前最长相等的前后缀长度 - 1(其实就是j)
B 使用next数组来做匹配
代码:
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; } }
459、重复的子字符串
具体实现:
A 计算前缀表,得到next数组
本题用-1的方式实现
B 使用next数组来做匹配
最长相等前后缀的长度为: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; } }