Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
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().
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Example 3:
Input: haystack = "", needle = ""
Output: 0
Constraints:
- 0 <= haystack.length, needle.length <= 5 * 104
- haystack and needle consist of only lower-case English characters.
class Solution {
public int strStr(String haystack, String needle) {
for(int i=0;;i++){
for(int j=0;;j++){
if(j==needle.length())return i;
if(i+j==haystack.length())return -1;
if(haystack.charAt(i+j)!=needle.charAt(j)) break;
}
}
}
}KMP算法
public String strStr(String haystack, String needle) {
//KMP algorithms
if(needle.equals("")) return haystack;
if(haystack.equals("")) return null;
char[] arr = needle.toCharArray();
int[] next = makeNext(arr);
for(int i = 0, j = 0, end = haystack.length(); i < end;){
if(j == -1 || haystack.charAt(i) == arr[j]){
j++;
i++;
if(j == arr.length){
return haystack.substring(i - arr.length);
}
}
if(i < end && haystack.charAt(i) != arr[j])
j = next[j];
}
return null;
}
private int[] makeNext(char[] arr){
int len = arr.length;
int[] next = new int[len];
next[0] = -1;
for(int i = 0, j = -1; i + 1 < len;){
if(j == -1 || arr[i] == arr[j]){
next[i+1] = j+1;
if(arr[i+1] == arr[j+1]) next[i+1] = next[j+1];
i++;
j++;
}
if(arr[i] != arr[j]) j = next[j];
}
return next;
}public class KMP {
/**
* @param s1
* 主串
* @param s2
* 模式串
* @return 如果匹配成功，返回下标，否则返回-1
*/
public static int KMP(String s1,String s2){
if(s1.length()<s2.length()||s2.length()==0||null==s2) return -1;
//求模式串的next数组
int[] next=new int[s2.length()];
next[0]=-1;
for(int i=1,k=-1;i<s2.length();i++){
if(k==-1||s2.charAt(i-1)==s2.charAt(k)){
k++;
next[i]=k;
}else {
next[i]=0;
k=0;
}
}
//进行匹配
for(int i=0,j=0;i<s1.length();){
if(s1.charAt(i)!=s2.charAt(j)){
if(next[j]==-1) i++;
else j=next[j];
}
else{
if(j==s2.length()-1) return i-s2.length()+1;
i++;j++;
}
}
return -1;
}
public static String getRandomString(int length) {//length表示生成字符串的长度
String base = "abcdefghijklmnopqrstuvwxyz0123456789";
Random random = new Random();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < length; i++) {
int number = random.nextInt(base.length());
sb.append(base.charAt(number));
}
return sb.toString();
}
public static void main(String args[]){
boolean falg=true;
int n=0;
while(n<10000){
String s1=getRandomString(new Random().nextInt(30));
String s2=getRandomString(new Random().nextInt(20)+1);
String s3=getRandomString(new Random().nextInt(10));
String s=s1+s3+s2;
if(KMP(s,s2)!=s.indexOf(s2)) {
System.out.println("s:" + s + " ,s2:" + s2);
falg = false;
}
n++;
}
if(falg) System.out.println("方法无误！");
}
}