第一种 暴力移位(效率低,资源浪费)
第二种KMP算法
这是直接盗用老师ppt中的内容,意思大家明白就好了,看代码:
public class KMP {
public int Index_KMP(String str1,String str2){
int i=0,j=-1;
int
arr[]=get_next(str2);
while(i
if(j==-1||str1.charAt(i)==str2.charAt(j)){
i++;
j++;
}
else j=arr[j];
}
if(j==str2.length())
return i-j;
return
-1;
}
public int[] get_next(String str){
int j=-1,i=0;
int
arr[]=new int[str.length()+1];
arr[0]=-1;
while(i
if(j==-1||str.charAt(i)==str.charAt(j)){
j++;
i++;
arr[i]=j;
}
else
j=arr[j];
}
return arr;
}
public static void main(String[]args)
{
KMP kmp=new KMP();
String T="abcac";
String s="ababcabcacbab";
int temp=kmp.Index_KMP(s,
T);
System.out.println();
System.out.println(temp);
}
}
有的书中或许是数组表示,这里直接用String是一样,有的可能是数组中t[0]保存的是数组的长度,这里是-1的处理。
例如判断一个字符串是不是另一个字符串的旋转,就可以利用KMP算法,具体解答步骤: