28. 实现 strStr()
题目
- BF算法
java">public int strStr(String s, String p) {
// 输入:haystack = "sa", needle = "ss"
//输出:0
// bf算法
int sLen = s.length();
int pLen = p.length();
for (int i = 0; i < sLen-pLen+1; i++) {
if(isEqual(s.substring(i,i+pLen),p)){
return i;
}
}
return -1;
}
private boolean isEqual(String str, String p) {
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != p.charAt(i)) {
return false;
}
}
return true;
}
java">public int strStr(String s, String p) {
// 输入:haystack = "aaaaabab", needle = "aaab"
// 输出:0
// kmp算法
// 构建next数组
int now = 0;
int x = 1;
int[] next = new int[p.length()];
next[0] = 0;
while (x < p.length()) {
// aadca....abc
//hello
if (p.charAt(now) == p.charAt(x)) {
now++;
next[x] = now;
x++;
}
// abcabd...abcabc
// 不相等则缩小now,缩小到next[now-1]
//
else if (now != 0) {
now = next[now-1];
}
// now为0
else {
next[x] = 0;
x += 1;
}
}
// 匹配
// 利用next数组来减少匹配次数
// aaaa ab aaab
int tar = 0;
int pos = 0;
int sLen = s.length();
int pLen = p.length();
while(tar < sLen) {
if (s.charAt(tar) == p.charAt(pos)) {
if (pos == pLen-1) return tar-pos;
tar++;
pos++;
}
// 若不相等,则移动pos到next[pos-1]
// tar在刚失配的地方
else if (pos != 0) {
pos = next[pos-1];
}
// 若第一位失配,则移动tar指针
else {
tar++;
}
}
return -1;
}
459.重复的子字符串
题目
- 超时
java">private static boolean isEqual(String str, String p) {
if (str.length() != p.length()) return false;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != p.charAt(i)) {
return false;
}
}
return true;
}
public static boolean repeatedSubstringPattern(String s) {
// 输入: s = "abab"
//输出: true
//解释: 可由子串 "ab" 重复两次构成。
// 1. 若为奇数,则截取前k个(1,2,3,...n/2)
//acdacd
//acd
// 2. 若为偶数,则子串
// ababab
int k = 1;
int group;
while (k <= s.length()/2) {
StringBuilder sb = new StringBuilder();
String p = s.substring(0, k);
group = s.length()/p.length();
for (int j = 0; j < group; j++) {
sb.append(p);
}
System.out.println("group:"+group);
System.out.println("s:"+s+",p:"+sb.toString());
if (isEqual(s,sb.toString())) {
return true;
}
k++;
}
return false;
}
- KMP的next数组方法
- 前面方法超时,因此我们思考,要找重复子字符串,与前缀后缀匹配相关,因此想到next数组
- 通过观察next数组,我们可以发现,若len可以被len-next[len-1]的值整除,则说明都是由重复子字符串构成。
证明
- 假设字符串s使用多个重复子串构成(这个子串是最小重复单位),重复出现的子字符串长度是x,所以s是由n * x组成。
- 因为字符串s的最长相同前后缀的的长度一定是不包含s本身,所以 最长相同前后缀长度必然是m * x,而且 n - m = 1,(这里如果不懂,看上面的推理)
- 所以如果 nx % (n - m)x = 0,就可以判定有重复出现的子字符串。
java">public static boolean repeatedSubstringPattern(String s) {
int now = 0;
int x = 1;
int[] next = new int[s.length()];
next[0] = 0;
while (x < s.length()) {
// aadca....abc
//hello
if (s.charAt(now) == s.charAt(x)) {
now++;
next[x] = now;
x++;
}
// abcabd...abcabc
// 不相等则缩小now,缩小到next[now-1]
//
else if (now != 0) {
now = next[now-1];
}
// now为0
else {
next[x] = 0;
x += 1;
}
}
// 找到第一个非0下标,加上最后一个的值 若为len,则true
if (next[s.length() - 1] != 0 && s.length() % (s.length() - (next[s.length() - 1])) == 0) {
return true;
}
return false;
}