题目
给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N,表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M,表示字符串 S 的长度。
第四行输入字符串 S。
输入: 3 aba 5 ababa
输出: 0 2
public class kmp { //初始化 public static int N = 1000010; public static char[] p = new char[N], s = new char[N]; public static int[] ne = new int[N]; public static void main(String[] args) throws IOException { //创建输出和输入流,防止数据过大超时 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); //导入p和s数组的数据, 注意,i初始为1,所以要用<= int n = Integer.parseInt(in.readLine()); String p_data = in.readLine(); for (int i = 1; i<=n; i++) {p[i] = p_data.charAt(i-1);} int m = Integer.parseInt(in.readLine()); String s_data = in.readLine(); for (int i = 1; i<=m; i++) {s[i] = s_data.charAt(i-1);} //构造next数组,也就是前缀下标数组,i从2开始是因为第一位和第一位比较永远是0,可以省略 //其实就相当于拿到前缀下标 for (int i = 2, j = 0; i<=n; i++) { while (j > 0 && p[i] != p[j+1]) {j = ne[j];} if (p[i] == p[j+1]) {j++;} ne[i] = j; } //kmp判断 //i指针为s,j指针为p for (int i = 1, j = 0; i<=m; i++) { //当j大于0且两个指针指向的值不相等时,将j赋值为ne[j] while (j > 0 && s[i] != p[j+1]) {j = ne[j];} //如果相等,那么就将j指针后移 if (s[i] == p[j+1]) {j++;} //如果j等于n了,也就是j等于我们要找的字串长度了,输出其开头下标, 然后再把j赋值为ne[j] if (j == n) { out.write(i-n + " "); j = ne[j]; } } //最后刷新输出 out.flush(); } }
kmp动画演示链接:kmp动画
不是我做的视频哈,不过做的真的很清晰,推荐看
今天又是三小时大战,人晕了,当我看到40分钟的课的时候我就意识到大的要来了呜呜呜
kmp算法果然无情(
声明:算法思路来源为y总,详细请见https://www.acwing.com/
本文仅用作学习记录和交流