Java版本KMP
https://leetcode-cn.com/problems/implement-strstr/
import java.util.Scanner; import java.lang.reflect.InvocationHandler; import java.lang.reflect.Proxy; public class Main { public int strStr(String haystack, String needle) { char []need = needle.toCharArray(); char []mun = haystack.toCharArray(); if(haystack.length()==0&&needle.length()==0){ return 0; } if(haystack.length()==0){ return -1; } if(needle.length()==0){ return 0; } int fir = -1; int j = -1; int snum = needle.length()+10; int []pre = new int[snum]; for (int i = 0;i<snum;i++){ pre[i] = -1; } for (int i=1;i<needle.length();i++){ while (j>-1&&need[j+1]!=need[i]){ j = pre[j]; } if (need[j+1]==need[i]){ j++; } pre[i] = j; //System.out.print(pre[i]+" "); } j=-1; for (int i = 0;i<haystack.length();i++){ while (j>-1&&mun[i]!=need[j+1]){ j = pre[j]; } if (mun[i]==need[j+1]){ j++; } if (j==needle.length()-1){ return i-j; } } return fir; } public static void main(String[] args) { Main main = new Main(); String a = "mississippi"; String b = "issip"; System.out.println(main.strStr(a,b)); } }
