假设有两个字符串A、B，要判断它们是否为旋转词，只需构造一个“A+A”字符串，再与B比较，若B为A的旋转词，则使用KMP算法是可以得到结果的
代码如下：
import java.util.*;
public class test {
public static boolean chkRotation(String A, String B) {
if(A.length()!=B.length()) return false;
String buf =new String(A+A);
int flag;
flag=kmp(buf,B);
if(flag==-1) return false;
else return true;
}
/* public static void getNext(String str ){
int[] next=new int[str.length()];
next[0]=-1;
char[] chars=str.toCharArray();
int i=0;
int j=-1;在java里面不能这么写
//"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；
//"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
while(i<str.length()){
if(j==-1||chars[i]==chars[j]){//此处的数组越界，报错
i++;
j++;
next[i]=j;
}
else
next[j]=j;
}
}
*/
public static int[] getNext(String str){
if(str.length()==-1) return new int[] {-1};
char[] chars=str.toCharArray();
int[] next=new int[str.length()];
next[0]=-1;
next[1]=0;
int pos=2;
int cn=0;
while (pos<str.length()){
if (chars[pos-1]==chars[cn]){
next[pos++]=++cn;
}
else if(cn>0) cn=next[cn];
else next[pos++]=0;
}
return next;
}
/*public static int kmp(String str, String pattern){
int i,j;
i=0;
j=0;
char[] chars=str.toCharArray();
int[] next=getNext(str);
while(i<str.length())
{
if(j==-1||chars[i]==chars[j])
{
i++;
j++;
}
else
{
j=next[j]; //消除了指针i的回溯
}
if(j==pattern.length())
return i-pattern.length();
}
return -1;
}
*/
public static int kmp(String ss,String ps){
if (ss.length()==0||ps.length()==0) return -1;
char[] chars=ss.toCharArray();
char[] charp=ps.toCharArray();
int i=0;//ss的指针
int j=0;//ps的指针
int[] next=getNext(ps);//这里相当于String B
while (i<ss.length()&&j<ps.length()){
if (j==-1||chars[i]==charp[j]){
i++;
j++;
}
else j=next[j];
}
if (j==ps.length()) return i-j;
else return -1;
}
public static int BFMatch(String str,String pattern){
char[] chars=str.toCharArray();
char[] charp=pattern.toCharArray();
/* int i=0; */
int charsi=0;
int charpi=0;
while(charsi<str.length()){
while(chars[charsi]==charp[charpi]){
charsi++;
charpi++;
}
if(charpi==str.length()-1)
return charsi-str.length();//找到匹配字符串中的匹配起始位置
charsi=charsi-charpi+1;
}
return -1;
}
public static void main(String[] args){
String str="RFSPUYLYR";
String pattern="UYLYRRFSP";
boolean f=chkRotation(str,pattern);
System.out.println(f);
System.exit(0);
}
}
如有不对欢迎指正！