- /**
- * 具体的匹配
- * @param str1
- * @param str2
- * @return
- */
- public int kMPMatcher(String str1,String str2){
- int i=0,j=-1;
- int arr[]=next(str2);
- while(i<str1.length()&&j<str2.length()){
- if(j==-1||str1.charAt(i)==str2.charAt(j)){
- i++;
- j++;
- }
- else j=arr[j];
- }
- if(j==str2.length())
- return i-j;
- return -1;
- }
- /**
- * next函数
- * @param str
- * @return
- */
- public int[] next(String str){
- int j=-1,i=0;
- int arr[]=new int[str.length()+1];
- arr[0]=-1;
- while(i<str.length()){
- if(j==-1||str.charAt(i)==str.charAt(j)){
- j++;
- i++;
- arr[i]=j;
- }
- else
- j=arr[j];
- }
- return arr;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1611201514018.html
来源: http://www.codesnippet.cn/detail/1611201514018.html