KMP字符串
理解KMP字符串
推荐文章(写的很好): KMP算法(研究总结,字符串)
题目 831
代码
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 = 10010; // 模板串的数据规模
static final int M = 100010; // 匹配字符串的数据规模
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();
}
}
为什么用System.out不通过,采用BufferedWriter就AC了呢
牛逼,我用Scanner超时了,抄楼主的,换成BufferReader就AC了