原題鏈接
題目：
給定一個模式串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
解題代碼：
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];
int n,m;
int main(){
cin >> n >> p + 1 >> m >> s + 1;
//初始化next陣列（尋找模板串中最長的公共前后綴）
for(int i = 2, j = 0; i <= n; i++){
while(j && p[i] != p[j + 1]) j = ne[j]; //前綴與后綴匹配失敗,使j回退到之前找到的公共前后綴的長度的位置，直到 p[i] 和 p[j + 1]匹配 或 j 回退到了起點（0的位置），
if(p[i] == p[j + 1]) j++; //前綴的i下標元素和后綴的j+1下標元素匹配成功，并繼續匹配下一個
ne[i] = j; //前i個數中的最長公共前后綴的長度為j，標記j的位置，以用來之后將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]; //j指標回退，繼續尋找下一個能匹配的位置
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225966.html
標籤：其他