AcWing 831. KMP字符串JAVA
原题链接
简单
作者:
理想二旬.
,
2021-05-07 22:20:17
,
所有人可见
,
阅读 306
JAVA 代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main{
private static int M = 1000010;
private static int N = 100010;
private static char[] p = new char[N];
private static char[] s = new char[M];
private static int[] ne = new int[N];
public static void main(String[] args) throws IOException{
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
String P = reader.readLine();
//子串
for(int i = 1,j = 0; i <= n; i++, j++){
p[i] = P.charAt(j);
}
int m = Integer.parseInt(reader.readLine());
String S = reader.readLine();
//待匹配的字符串
for(int i = 1,j = 0; i <= m; i++,j++){
s[i] = S.charAt(j);
}
//求next数组过程,ne数组存储的是以i为终点,后缀与前缀相等的最大长度
//i从2开始,因为1的终点和起点都是1
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匹配过程
//y总习惯---字符数组从下标1开始
for(int i = 1, j = 0; i <= m; i++){
//匹配到第i个字符的时候,匹配失败,则从ne[j]开始重新匹配
while(j != 0 && s[i] != p[j + 1])
j = ne[j];
if(s[i] == p[j + 1])
j++;
if(j == n){
//匹配成功
writer.write(i - n + " ");
//再重新开始匹配
j = ne[j];
}
}
writer.flush();
reader.close();
writer.close();
}
}