旋轉詞：把字符串str的任意部分移動到后面形成的新字符串叫做字符串str的旋轉詞。
比如abc的旋轉詞有 abc,acb，cba，...
判斷str1和str2是否互為旋轉詞，其最優解可以是時間復雜度為O（n）（n為字符串的長度）
方法如下：
1、判斷長度是否相等
2、長度相等的話就構建大字符串，str1+str1（str1+str1中包含了str1的所有旋轉詞）
3、用KPM算法判斷大字符串中是否包含str2
下面是具體算法實現，必須先了解KPM算法才行
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
package k;import java.util.Scanner;public class test1 { static int[] next; //next數組 static String str1; //字符串str1 static String str2; //字符串str2 static String str; //字符串str=str1+str1 public static void main(String[] args) { Scanner in = new Scanner(System.in); str1 = in.next(); //獲取輸入的第一個字符串 str2 = in.next(); //獲取輸入的第二個字符串 if (str1.length() != str2.length()) //如果長度不相等，那么就肯定不是互為旋轉詞 System.out.println(str1 + "與" + str2 + "不是互為旋轉詞"); else { str = str1 + str1; makeNext(); //構建next數組 check(); //判斷是否為旋轉詞 } } private static void check() { int i = 0; int j = 0; while (i < str2.length() && j < str.length()) if (i == -1 || str2.charAt(i) == str.charAt(j)) { i++; j++; } else { i = next[i]; } if (i >= str2.length()) System.out.println(str1 + "與" + str2 + "互為旋轉詞"); else System.out.println(str1 + "與" + str2 + "不是互為旋轉詞"); } private static void makeNext() { next = new int[str2.length()]; int i = 0; int k = -1; next[0] = -1; while (i < str2.length() - 1) { while (k >= 0 && str2.charAt(i) != str2.charAt(k)) k = next[k]; i++; k++; if (str2.charAt(i) == str2.charAt(k)) next[i] = next[k]; else next[i] = k; } }} |
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/tangZH/p/6655984.html
