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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| /**
* KMP算法特性分析
*/
public class KMPAnalysis {
/**
* 分析不同模式串的匹配效率
*/
public static void analyzePatternTypes() {
System.out.println("=== KMP算法特性分析 ===\n");
String[] testTexts = {
"AAAAAAAAAAAAAAAB",
"ABCDEFGHIJKLMNOP",
"ABABABABABABAB",
"The quick brown fox jumps over the lazy dog"
};
String[] testPatterns = {
"AAAAB", // 重复字符模式
"DEFGH", // 无重复模式
"ABABAB", // 周期性模式
"brown fox" // 实际单词
};
for (int i = 0; i < testTexts.length; i++) {
String text = testTexts[i];
String pattern = testPatterns[i];
System.out.println("测试 " + (i + 1) + ":");
System.out.println("文本: " + text);
System.out.println("模式: " + pattern);
// 分析失败函数特征
int[] pi = KMPAlgorithm.buildFailureFunction(pattern);
analyzeFailureFunction(pattern, pi);
// 执行匹配并分析
long startTime = System.nanoTime();
int result = KMPAlgorithm.kmpSearch(text, pattern);
long elapsed = System.nanoTime() - startTime;
System.out.printf("匹配结果: %s%n", result != -1 ? "位置 " + result : "未找到");
System.out.printf("执行时间: %.3f μs%n", elapsed / 1000.0);
System.out.println("-".repeat(40));
}
}
/**
* 分析失败函数的特征
*/
private static void analyzeFailureFunction(String pattern, int[] pi) {
int maxJump = 0;
int totalJumps = 0;
int nonZeroCount = 0;
for (int i = 1; i < pi.length; i++) {
if (pi[i] > 0) {
nonZeroCount++;
totalJumps += pi[i];
maxJump = Math.max(maxJump, pi[i]);
}
}
double avgJump = nonZeroCount > 0 ? (double) totalJumps / nonZeroCount : 0;
System.out.println("失败函数分析:");
System.out.printf(" 最大跳转: %d%n", maxJump);
System.out.printf(" 平均跳转: %.2f%n", avgJump);
System.out.printf(" 跳转比例: %.2f%%%n", 100.0 * nonZeroCount / (pi.length - 1));
}
/**
* 边界情况测试
*/
public static void testEdgeCases() {
System.out.println("\n=== 边界情况测试 ===");
Object[][] testCases = {
{"空模式串", "Hello World", ""},
{"空文本串", "", "Hello"},
{"单字符匹配", "A", "A"},
{"单字符不匹配", "A", "B"},
{"模式串比文本长", "Hi", "Hello"},
{"完全匹配", "Hello", "Hello"},
{"重复字符", "AAAA", "AA"},
{"Unicode字符", "你好世界", "世界"}
};
for (Object[] testCase : testCases) {
String description = (String) testCase[0];
String text = (String) testCase[1];
String pattern = (String) testCase[2];
System.out.printf("%-15s: ", description);
try {
int result = KMPAlgorithm.kmpSearch(text, pattern);
System.out.printf("结果=%d%n", result);
} catch (Exception e) {
System.out.printf("异常: %s%n", e.getMessage());
}
}
}
public static void main(String[] args) {
analyzePatternTypes();
testEdgeCases();
}
}
|