题目描述
给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N,表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M,表示字符串S的长度。
第四行输入字符串S。
输出格式
共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。
数据范围
1≤N≤105
1≤M≤106
输入样例:
3
aba
5
ababa
输出样例:
0 2
这道题确实比较抽象,不好理解,可以配合y总的视频和下面的博客一起,会更好理解一些
推荐博客:KMP算法
Java代码
import java.io.*;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
static final int N = 100010; // 模板串的数据规模 注意范围
static final int M = 1000010; // 匹配字符串的数据规模
static char[] p = new char[N]; // 模板串
static char[] s = new char[M]; // 被匹配字符串
static int[] next = new int[N]; // next数组
public static void main(String[] args) throws IOException {
// 对输入数据进行初始化
int n = Integer.parseInt(reader.readLine()); // 模板串的长度
String pStr = reader.readLine();
for (int i = 1; i <= n; i++) p[i] = pStr.charAt(i - 1);
int m = Integer.parseInt(reader.readLine()); // 被匹配字符串的长度
String sStr = reader.readLine();
for (int i = 1; i <= m; i++) s[i] = sStr.charAt(i - 1);
// 求 next的过程
for (int i = 2, j = 0; i <= n; i++) {// i = 1的时候只有一个元素, 最长前缀的长度为 0
while (j != 0 && p[i] != p[j + 1]) j = next[j];
if (p[i] == p[j + 1]) j++;
next[i] = j;
}
// kmp匹配过程
// i指向 s将要匹配的位置, j指向已经匹配模板串已经匹配成功的位置
for (int i = 1, j = 0; i <= m; i++) {
while (j != 0 && s[i] != p[j + 1]) j = next[j]; // 进行 next跳转
// 继续进行匹配, 如果此时模板串的字符和被匹配字符串的字符相等, 继续向下进行匹配++
if (s[i] == p[j + 1]) j++;
// 如果匹配成功
if (j == n) {
log.write(i - n + " "); // 将 s串中起点的位置写入
j = next[j]; // 进行 next跳转
}
}
log.flush(); // 关闭输入输出流
reader.close();
log.close();
}
}