string kmp java
string kmp java
KMP 算法的 Java 实现
public class KMP {
// 构建 pattern 部分匹配表（next数组）
private static int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = 0; // 第一个字符的最长相等前后缀长度为0
int j = 0; // 前缀末尾指针
// 从第二个字符开始计算
for (int i = 1; i < pattern.length(); i++) {
// 当前字符不匹配时，回退到前一个最长前缀的末尾
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
// 当前字符匹配，最长相等前后缀长度加1
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
// KMP搜索算法
public static void kmpSearch(String text, String pattern) {
if (text == null || pattern == null || pattern.length() == 0 ||
text.length() < pattern.length()) {
return;
}
int[] next = getNext(pattern);
int j = 0; // 模式串的指针
// 遍历主串
for (int i = 0; i < text.length(); i++) {
// 不匹配时，根据next数组移动模式串指针
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
// 当前字符匹配，模式串指针前进
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
// 找到完整匹配
if (j == pattern.length()) {
System.out.println("模式串在位置 " + (i - j + 1) + " 处找到匹配");
// 继续寻找下一个匹配
j = next[j - 1];
}
}
}
// 主方法，包含测试用例
public static void main(String[] args) {
String text = "ABABCABCABABAD";
String pattern = "ABCABA";
System.out.println("主串：" + text);
System.out.println("模式串：" + pattern);
System.out.println("查找结果：");
kmpSearch(text, pattern);
// 打印next数组，用于理解
System.out.println("\nNext数组：");
int[] next = getNext(pattern);
for (int i = 0; i < next.length; i++) {
System.out.print(next[i] + " ");
}
}
}
代码说明
-
类结构
- 包含三个主要方法：
getNext()、kmpSearch()和main() - 所有方法都是静态的，可以直接调用
- 包含三个主要方法：
-
getNext() 方法
- 构建模式串的部分匹配表（next数组）
next[i]表示模式串中以第i个字符结尾的子串的最长相等前后缀长度。- 时间复杂度：O(m)，m为模式串长度
- 使用双指针技术计算最长相等前后缀
-
kmpSearch() 方法
- 实现 KMP 匹配算法的主要逻辑。
- 遍历主串，利用
next数组在匹配失败时快速跳转到模式串的下一个可能匹配位置 (移动模式串，使得前缀移动到后缀的位置) 1。 - 如果模式串完全匹配，打印匹配的起始索引。
- 时间复杂度：O(n)，n为主串长度
- 包含输入验证
- 可以找到所有匹配位置
-
main() 方法
- 包含测试用例
- 展示如何使用 KMP 算法
- 打印 next 数组以帮助理解
最长相等前后缀
双指针算法是计算最长相等前后缀（也称为部分匹配表或 next 数组）的一种简洁高效的方法，常用于 KMP 算法。对于一个字符串，其最长相等前后缀是指：
- 字符串的前缀和后缀相等
- 且这个前缀和后缀不包含整个字符串本身
- 在所有满足条件的前后缀中，长度最长的那一对
部分匹配表的本质是为模式串的每个位置记录对应的子串的 “最长相等前后缀” 的长度。
例如，对于字符串 “abcabc”：
- 前缀集合: a, ab, abc, abca, abcab
- 后缀集合: c, bc, abc, cabc, bcabc
- 相等的前后缀: “abc”
- 最长相等前后缀长度: 3
以模式串 “ABABCABAA” 为例说明双指针如何计算 next 数组, 查找最长相等前后缀 ：
- 初始化：
next[0] = 0（第一个字符的最长相等前后缀长度为0）j = 0（前缀指针初始位置）i = 1（从第二个字符开始）
- 从左到右遍历模式串：
- 当
i指向的字符与j指向的字符不匹配时，前缀指针j回退到next[j-1] - 当
i指向的字符与j指向的字符匹配时，j向前移动一位 - 当前位置的最长相等前后缀长度
next[i] = j
- 当
- 计算过程示例（模式串 “ABABCABAA”）：
- 初始：
next[0] = 0 i=1, j=0: 比较 B 和 A，不匹配，j=0，next[1]=0i=2, j=0: 比较 A 和 A，匹配，j=1，next[2]=1i=3, j=1: 比较 B 和 B，匹配，j=2，next[3]=2i=4, j=2: 比较 C 和 A，不匹配，j=next[1]=0，再比较 C 和 A，不匹配，j=0，next[4]=0i=5, j=0: 比较 A 和 A，匹配，j=1，next[5]=1i=6, j=1: 比较 B 和 B，匹配，j=2，next[6]=2i=7, j=2: 比较 A 和 A，匹配，j=3，next[7]=3i=8, j=3: 比较 A 和 B，不匹配，j=next[2]=1，再比较 A 和 B，不匹配，j=next[0]=0，再比较 A 和 A，匹配，j=1，next[8]=1
- 初始：
最终的 next 数组：[0, 0, 1, 2, 0, 1, 2, 3, 1]
使用示例
// 创建测试用例
String text = "ABABCABCABABAD";
String pattern = "ABCABA";
KMP.kmpSearch(text, pattern);
输出示例
主串：ABABCABCABABAD
模式串：ABCABA
查找结果：
模式串在位置 5 处找到匹配
Next数组：
0 0 0 1 2 1
算法特点
-
效率
- 总时间复杂度：O(m + n)
- 空间复杂度：O(m)
- 避免了朴素匹配算法中的回溯
-
优势
- 在主串中只需要遍历一次
- 利用已经匹配的信息避免重复比较
- 特别适合在长文本中查找模式串
-
应用场景
- 文本编辑器的查找功能
- DNA序列匹配
- 网络入侵检测系统
- 任何需要字符串匹配的场景
注意事项
-
边界处理
- 代码中包含了对 null 和空字符串的检查
- 处理了模式串长度大于主串的情况
-
扩展性
- 可以轻松修改代码以返回所有匹配位置的列表
- 可以添加计数功能统计匹配次数
-
调试
- 包含了 next 数组的打印功能，便于理解和调试
- 可以根据需要添加更多的调试信息
Question One 2 3
[!NOTE]
最小循环子数组 给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。 输入描述 第一行输入数组中元素个数n，1 <= n <= 100000 第二行输入数组的数字序列nums，以空格分割，0 <= nums[i]<= 10 输出描述 输出最小的子数组的数字序列，以空格分割; 备注 数组本身是其最大的子数组，循环1次可生成的自身 示例1: 输入 9 1 2 1 1 2 1 1 2 1 输出 1 2 1 说明 数组[1,2,1,1,2,1,1,2,1]可由子数组[1,2,1]重复循环3次拼接而成
Question Two 4
[!NOTE]
实现strstr
题目描述
返回指定子串在字符串中第一次出现处的索引，如果此字符串中没有这样的子串，则返回 -1。
输入描述
第一行输入主串
第二行输入子串
输出描述
输出子串在主串中的首次出现的下标位置，如果没有则返回 -1。
用例
输入 abcdabcdabcd
bcd输出 1 说明 无
参考:
移动模式串，使得前缀移动到后缀的位置。可以证明中间没有匹配的情况。模式串最长前缀移动到最长后缀位置时中间可能会有遗漏的匹配的情况 命题不成立 ↩︎
最小循环子数组 ↩︎
最小循环子数组 ↩︎
实现strstr ↩︎