Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1
if needle is not part of haystack.Example 1:
Input: haystack = “hello”, needle = “ll” Output: 2 Example 2:
Input: haystack = “aaaaa”, needle = “bba” Output: -1 Clarification:
What should we return when needle is an empty string? This is a great
question to ask during an interview.For the purpose of this problem, we will return 0 when needle is an
empty string. This is consistent to C’s strstr() and Java’s indexOf().
需要注意边界条件，例如把正常逻辑全放到对 haystack 的循环体中，但 haystack 可能为空，逻辑将会走不到
public int strStr(String haystack, String needle) {char[] a1=haystack.toCharArray();
char[] a2=needle.toCharArray();
if(a2.length==0) return 0;
for(int i=0;i<a1.length;i++){
boolean flag=true;
for(int j=0;j<a2.length;j++){if(i+j>=a1.length || a1[j+i]!=a2[j]) {
flag=false;
break;
}
}
if(flag) return i;
}
return -1;
}上面的复杂度是 o(n*m), 在某些重复串较多的情况下，时间不理想，上面的使用暴力匹配的思想，可以用 KMP 算法来优化
KMP 的原理和回文串的马拉车算法类似，利用已有的信息去除一些无用的判断
例如
P：ABCABC D……
T：ABCABC E
这个时候判断
ABCABC D……
ABCAB CE
是没有意义的
因为当需要回溯找串的时候需要保证
23456==12345
123456 7……
12345 68
而上面的关系完全取决于 T 自己，可以提前计算，也就是说我们在发生不匹配的时候，可以直接确定需要相对移动的值，不需要完全回溯
我们的问题转化为
T：ABCABCABCABC Y
T’：ABCABCABCABC
在 Y 位上发生不匹配后，确定所有的 k 位满足 T’的前 k 位等于后 k 位
这样看起来储存 k 位置的是个二维结构，
看上面的例子，这时候看起来需要回溯的情况为 [ABC,ABCABC,ABCABCABC]
有一个不容易发现的问题
{n1 n1}
{n2 n2}
当 k1>k2 时，k2 一定是 k1 的子串，这样就能形成线性结构，这就是 next 数组，求 next 数据是一个动态规划的过程
我们定义 next[k]是 k 位置之前前缀和后缀重合最大的长度
public int strStr(String haystack, String needle) {char[] a1=haystack.toCharArray();
char[] a2=needle.toCharArray();
int l1=a1.length;
int l2=a2.length;
if(l2==0) return 0;
int[] next=new int[l2];
for(int i=2;i<l2;i++){int t=next[i-1];
while(t!=-1){if(a2[t]==a2[i-1]) {next[i]=t+1;
break;
}
else {if(t==0) break;
t=next[t];
}
}
}
int i=0;
int j=0;
while(i<l1 && j<l2){if(a1[i]==a2[j]){
i++;
j++;
}else{if(next[j]!=0){j=next[j];
}else{
i=i-j+1;
j=0;
}
}
}
return j==l2?i-j:-1;
}