算法三十一：字符串匹配

忘是亡心i 2022-05-21 09:08 124阅读 0赞

### **问题描述** ###

给定一个大串 A 和一个模式串 B，求 B 在 A 的哪些位置出现（输出这些出现位置的起始位置，下标从 0 开始）。

### **输入格式** ###

第一行一个正整数 n，表示串 A 的长度。

第二行包含一个长度为 n 的串 A。

第三行一个正整数 m，表示串 B 的长度。

第四行包含一个长度为 m 的串 B。

保证串 A,B 只包含小写字母。

### **输出格式** ###

对于每个 B 在 A 中出现的位置，输出单独一行一个整数表示该次出现的起始位置。

对于所有的这些位置，请升序（从小到大）输出。

### **样例输入** ###

7
    abcabca
    4
    abca

### **样例输出** ###

0
    3

### **提示** ###

\[此题是单模匹配算法的练习题。\]

\[可以尝试暴力匹配、KMP算法、Boyer-Moore算法、Rabin-Karp算法，并比较它们的效果。\]

### **一. 伪代码** ###

![70][]

### **二. 具体实现** ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
vector<int> Next;  
// 这是匹配函数，将所有匹配位置求出并返回  
// n：串 A 的长度  
// A：题目描述中的串 A  
// m：串 B 的长度  
// B：题目描述中的串 B  
// 返回值：一个 vector<int>，从小到大依次存放各匹配位置  
vector<int> match(int n, string A, int m, string B) \{  
Next.resize(m);  
int j = Next\[0\]= -1;  
for(int i =1; i<m; ++i)\{  
while( j >= 0 &&B\[i\] != B\[j+1\])  
j = Next\[j\];  
if(B\[i\] == B\[j+1\])  
\++j;  
Next\[i\] = j;  
\}  
j = -1;  
vector<int> ans;  
for(int i=0; i<n; ++i)\{  
while(j >=0 &&A\[i\] != B\[j+1\])  
j = Next\[j\];  
if(A\[i\] == B\[j+1\])  
\++j;  
if(j == m-1)  
ans.push\_back(i-m+1);  
\}  
return ans;  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220521/502ea2d8c253498abf2f247408dcc837.png