题目描述
给定一个模式串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
求关注~~~
思路
从图中,我们观察到kmp中字符的匹配F, E不相等,那么模板匹配依据之前模板与模板之间的比较的内容,跳过n个格子
这就是利用kmp的精髓之处
//求next的过程,同kmp(请先了解约定条件),由于所有的p从1存储,模板与模板的匹配,需要错开i = 1相同的位置,利用i = 2进行模板匹配
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; //当前点匹配,则记录当前点的下一个点j(j++)在模板中的位置
cout << ne[i] << " ";
//匹配成功下
//ababaa ababaa
/*
1. ababaa ab a != b 0
ababaa
while(j = 0 && p[2] != p[1]) j = ne[j]; => 跳过
if(p[2] == p[0 + 1]) j ++; =>跳过
ne[i] = j; => ne[2] = 0
2. ababaa aba a = a ab != ba 1
ababaa
while(j = 0 && p[3] != p[1]) j = ne[j]; => 跳过
if(p[3] == p[1]) j ++; => j = 1
ne[i] = j; => ne[3] = 1 最多有一个字符匹配
3. ababaa abab ab = ab 2
ababaa
while(j = 1 && p[4] != p[2]) j = ne[j]; => 跳过
if(p[3] == p[1]) j ++; => j = 2
ne[i] = j; => ne[4] = 2 最多有两个字符匹配
4. ababaa ababa aba = aba 3
ababaa
while(j = 2 && p[5] != p[3]) j = ne[j]; => 跳过
if(p[3] == p[1]) j ++; => j = 3
ne[i] = j; => ne[5] = 3 最多有三个个字符匹配
5. ababaa ababaa a = a 1
ababaa
while(j = 2 && p[6] != p[4]) j = ne[j]; => j = ne[3] = 1
ababaa
ababaa
while(j = 1 && p[6] != p[2]) j = ne[j]; => j = ne[1] = 0 (1位置在数组中默认为0)
ababaa
ababaa
while(j = 0 && p[6] != p[2]) j = ne[j]; => 跳过
if(p[6] == p[1]) j ++; => j = 1
ne[i] = j; => ne[6] = 1 最多有1个字符匹配
*/
}
//kmp匹配过程
//s, p是从1位置开始进行匹配
//约定 字符比较s[i]是否等于p[j + 1] 所以i = 1, j = 0,
//规定j = next[j],其中j为当前匹配字符的前一个完全匹配的坐标点,
// 1.当j = 0,表示前面没有字符(从头开始),没有匹配的next,因为p能够比较的字符位置在1
// 2.当s[i] != p[j + 1] 查找j = next[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){
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
java
import java.io.*;
public class Main{
static int n, m;
static char[] p = new char[100010], s = new char[1000010];
static int[] ne = new int[100010];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String sp = br.readLine();
int m = Integer.parseInt(br.readLine());
String ss = br.readLine();
for(int i = 1; i <= n; i ++){
p[i] = sp.charAt(i - 1);
}
for(int i = 1; i <= m; i ++){
s[i] = ss.charAt(i - 1);
}
//ne
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; //当前点匹配,则记录当前点的下一个点j(j++)在模板中的位置
}
for(int i = 1, j = 0; i <= m; i ++){
while(j != 0 && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j ++;
if(j == n){
bw.write(i - n +" ");
j = ne[j];
}
}
bw.flush();
bw.close();
br.close();
}
}
python3
N = 100010
M = 1000010
p = [0] * N
ne = [0] * N
s = [0] * M
def main():
global p, ne, s;
n = int(input())
p = list(input())
p.insert(0, 0)
m = int(input())
s = list(input())
s.insert(0, 0)
#ne
i, j = 2, 0
while(i <= n):
while(j and p[i] != p[j + 1]): j = ne[j]
if(p[i] == p[j + 1]): j += 1
ne[i] = j
i += 1
i, j = 1, 0
while(i <= m):
while(j and s[i] != p[j + 1]): j = ne[j]
if(s[i] == p[j + 1]): j += 1
if(j == n):
print(i - n, end=" ")
j = ne[j]
i += 1
main()
c++
#include <iostream>
using namespace std;
const int N = 100100, M = 1000100;
int n, m;
char p[N], s[M];
int ne[N];
int main(){
cin >> n >> p + 1 >> m >> s + 1;
//求next的过程,同kmp,由于所有的p从1存储,模板与模板的匹配,需要错开i = 1相同的位置,利用i = 2进行模板匹配
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; //当前点匹配,则记录当前点的下一个点j(j++)在模板中的位置
cout << ne[i] << " ";
//匹配成功下
//ababaa ababaa
/*
next[2] = 0
next[3] = 1
next[4]的情况 abab
abab aa i = 4
ab abaa j 从 0 开始, j = 1, p[i] = p[j + 1]相等 j = j + 1 = 2
=>next[4] = 2
*/
}
//kmp匹配过程
//s, p是从1位置开始进行匹配
//约定 字符比较s[i]是否等于p[j + 1] 所以i = 1, j = 0,
//规定j = next[j],其中j为当前匹配字符的前一个完全匹配的坐标点,
// 1.当j = 0,表示前面没有字符(从头开始),没有匹配的next
// 2.当s[i] != p[j + 1] 查找j = next[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){
printf("%d ", i - n);
j = ne[j];
}
}
return 0;
}