AcWing 831. KMP字符串
原题链接
简单
作者:
江上荷人
,
2024-04-08 22:25:45
,
所有人可见
,
阅读 1
public class Main{
static final int N = 100010;
static int[] next = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder builder = new StringBuilder();
int n = Integer.parseInt(br.readLine());
//计数字符串时下标从1开始,所以加空格
String p = " "+br.readLine(); //模式串
char[] a1 = p.toCharArray();
int m = Integer.parseInt(br.readLine());
String s = " "+br.readLine(); //主串
char[] a2 = s.toCharArray();
/**
构造模式串的next数组
模式串下标从1开始计数, 由于a1[1]=0,i从2开始
j代表前后缀相等个数,所以从0开始,每次比较 a1[i]和a1[j+1]
*/
for(int i = 2,j = 0;i <= n ;i++) {
//要先判断是否不等于,因为回退后可能等于
while(j!=0&&a1[i]!=a1[j+1]) j = next[j];
if(a1[i]==a1[j+1]) j++;
//每次都要确定next数组
next[i] = j;
}
/**
模式匹配
字符串都从1开始计数 主串的i 和模式串的j+1进行比较
当主串下标s1和模式串下标p1的字符不匹配时,s1先不动,我们要寻找模式串的某个下标来和s1对比,
假设找到了模式串的下标p2,那么表明模式串下标p2之前的字符和主串s1之前的(p2-1)个字符全部匹配,
这样模式串就产生了前后缀相等的情况,从而加以利用
*/
for(int i = 1,j = 0; i <= m;i++) {
while(j!=0&&a2[i]!=a1[j+1]) j = next[j];
if(a2[i]==a1[j+1]) j++;
if(j==n) {
j = next[j]; //可能有多个模式串接着遍历,
//结果要保存从0开始的下标,所以是 i-n而不是i-n+1
builder.append(i - n).append(" ");
}
}
br.close();
System.out.println(builder);
}
}