2023-11-14
作用：从一个字符串中找到另一个字符串的位置
思路：
暴力匹配-》主串的指针一直往前走，不后退-》匹配串的指针回退的位置变小-》根据前缀表
求前缀表（匹配串的所有前缀的最长公共前后缀长度表）：
/求前缀表
int[] next=new int[needle.length()];
next[0]=0;
int val=0;
for(int i=1;i<needle.length();i++){
while(val>0 && needle.charAt(i)!=needle.charAt(val)){
val=next[val-1];
}
if(needle.charAt(i)==needle.charAt(val)){
val++;
}
next[i]=val;
}
kmp算法：
//kmp
for(int i=0,j=0;i<haystack.length();i++){
while(j>0 && haystack.charAt(i)!=needle.charAt(j)){//先j退，不相等继续退，可能会退到0
j=next[j-1]; //最前面next[0]是0，不用特别注意
}
if(haystack.charAt(i)==needle.charAt(j)){
//i++; //i放在这，可能全部首字母都不匹配呢
j++;
}
if(j==needle.length()){
return i-j+1;
}
}
return -1;
全部代码：
class Solution {
public int strStr(String haystack, String needle) {
//暴力法
//双指针
//kmp算法
//求前缀表
int[] next=new int[needle.length()];
next[0]=0;
int val=0;
for(int i=1;i<needle.length();i++){
while(val>0 && needle.charAt(i)!=needle.charAt(val)){
val=next[val-1];
}
if(needle.charAt(i)==needle.charAt(val)){
val++;
}
next[i]=val;
}
//kmp
for(int i=0,j=0;i<haystack.length();i++){
while(j>0 && haystack.charAt(i)!=needle.charAt(j)){//先j退，不相等继续退，可能会退到0
j=next[j-1]; //最前面next[0]是0，不用特别注意
}
if(haystack.charAt(i)==needle.charAt(j)){
//i++; //i放在这，可能全部首字母都不匹配呢
j++;
}
if(j==needle.length()){
return i-j+1;
}
}
return -1;
}
}