题目描述
题目:给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N,表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M,表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。
数据范围
$1≤N≤10^5$
$1≤M≤10^6$
样例
输入样例:
3
aba
5
ababa
输出样例:
0 2
这里y总给出的模板求next数组与之前做的严蔚敏数据结构笔记里给出的next数组表示法有些许不同。
严蔚敏数据结构里的next数组记录的是当前位置匹配失败后,模式串应该移动到哪个位置,如下:当E匹配失败时,则去让模式串第2个位置继续匹配。
模式串 | A | B | C | A | E |
---|---|---|---|---|---|
next[]: | 0 | 1 | 1 | 1 | 2 |
y总给出的模板里的next数组记录的是,以当前位置截止的子串的前后缀字符长度是多少,如下:当E匹配失败时,next[E]=0,说明ABCAE这一子串前后缀字符长度为0,所以将j指针回溯到0,然后每次将j指向的下一位去继续与主串比较。
模式串 | A | B | C | A | E |
---|---|---|---|---|---|
next[]: | 0 | 0 | 0 | 1 | 0 |
所以这里起初j指向0(j也可以理解为当前匹配到的最大前后缀子串长度),求next数组时,就是在模式串中找每个子串前后缀的过程,将next[1]=0(数组从1号下标开始使用),然后将i指向2(从第2个字符开始记录前后缀子串长度),然后将j指向的下一位与i指针指向的字符进行比较,i指针不回溯:
- 若j+1的位置和i指向位置匹配,则说明最大前后缀子串长度多1,即
j++;
- 若j指向数的下一个位置和i指向位置不匹配,则将j回溯到next[j],因为j记录的是当前最大前后缀子串长度,即j指向的也是最大前缀的最后一个位置,i指向的是最大后缀末尾的下一个位置,而最大前缀和最大后缀是相等的,此时让j=next[j]就是代表让j回到最大前缀这个子串的最大前缀位置,然后让j+1的位置与i指向的位置去匹配。具体过程参照下图。
求next数组代码如下:
//求next数组
for(int i=2, j=0; i<=n; i++){
while(j && p[i] != p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
当有next数组之后,只需要将模式串与主串依次匹配,i指针遍历主串不回溯,j指针指向模式串当前要匹配字符的前一个位置,当p[j+1]!=s[i]时,让j指针回溯到next[j]的位置即可。题目的完整代码如下:
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
int n, m;
char p[N], s[M];
int ne[N];
int main(){
cin>>n>>p+1>>m>>s+1;
//ne[1] = 0;
//求next数组
for(int i=2, j=0; i<=n; i++){
while(j && p[i] != p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
//匹配主串
for(int i=1, j=0; i<=m; i++){
while(j && s[i] != p[j+1]) j = ne[j];
if(s[i] == p[j+1]) j++;
if(j == n){
cout<< i-j << " ";
j = ne[j];
}
}
return 0;
}