【模板】字符串匹配的三种做法（Hash、KMP、STL）

时间：2021-11-02 12:03:57

题目描述

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

输入输出格式

输入格式：

第一行为一个字符串，即为s1

第二行为一个字符串，即为s2

输出格式：

1行，包含若干整数，表示s2在s1中出现的位置，中间用空格隔开。

输入输出样例

输入样例#1：　　　　　　　　　　　　　　　　　　　　　输出样例#1：

ABABABC 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1 3

ABA

很明显，这道题可以用暴力求解字符串匹配。即枚举起点，然后判断是否为子串。时间复杂度为$O(len^2)$.复杂度明显超时。
Hash：
一种用正确率换取时间的算法，可以把每个字符串看作是一个b进制下的数，求出它在10进制下的值，然后在与几个质数取模，得到在(long long) | (int)范围内可储存的值，这种情况下我们认为同一hash值的字符串相同。
在一般情况下，不会有人专门卡Hash，所以也可以不取模，定义一个(unsigned long long) 让它自然溢出。
思路如下：预处理出每一个$b^i$和A串的前缀Hash，枚举A串的起点，求出从$i$到$i+len(B)$的hash值，与B的hash值比较，时间复杂度是$O(n)$。

代码如下：

 #include<bits/stdc++.h>

 const int b = ;

 typedef unsigned long long pmod;

 char s1[], s2[];

 pmod sum[];

 pmod p[];

 int main(){

     p[] = , sum[] = ; pmod s = ;

     for(int i=; i<; i++)//预处理

         p[i] = p[i-]*b;

     scanf("%s%s", s1+, s2+);

     int n = strlen(s1+), m = strlen(s2+), cnt=;

     for(int i=; i<=n; i++)//预处理出A串的前缀Hash值

         sum[i] = sum[i-]*b+(pmod)(s1[i]-'A');

     for(int i=; i<=m; i++)

         s = s*b+(pmod)(s2[i]-'A');

     for(int i=; i<=n-m; i++)//枚举起点

         if(s == sum[i+m]-sum[i]*p[m]) cnt++;

     printf("%d\n", cnt);

     return ;

 }

KMP：
将A串称为模式串，B串成为主串。
枚举每个模式串终点$i$，判断主串能匹配的长度$j$。$j$同时为主串上匹配的位置
匹配成功$i++, j++$.
在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
也就是将匹配长度$j$由当前位置变为上一个可以匹配的位置
如此可以在$O(n)$的时间复杂度内完成匹配
代码如下：





 #include<bits/stdc++.h>

 using namespace std;

 const int N = ;int next[N];char a[N], b[N];

 int main() {

     scanf("%s%s", a+, b+);

     int n=strlen(a+), m=strlen(b+), j=;

     next[]=;

     for(int i=; i<m; i++) {

         while(j> && b[j+] != b[i+]) j=next[j];

         if(b[i+] == b[j+]) j++;

         next[i+]=j;

     }j=;

     for(int i=; i<n; i++) {

         while(j> && b[j+] != a[i+]) j=next[j];

         if(a[i+] == b[j+]) j++;

         if(j==m) {printf("%d\n", i-j+, i, j);j=next[j];}

     }

     for(int i=;i<=m;i++) printf("%d ", next[i]);

     return ;

 }




STL：


c++最强大的功能就是STL，它可以使代码很简洁，但同时会降低代码的效率（因为频繁的调用），但是，考试中使用STL也是一种好的办法，可以大大降低编程的时间。


本题可以使用STL中string的find()函数和其中表示string类型允许的最大值npos。


代码如下：




#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

int main(){

    string s, c;

    int ans=, p=-;

    getline(cin, s);

    getline(cin, c);

    while((p=s.find(c, p+))!=string::npos) ans++;

    printf("%d", ans);

    return ;

}




非常简洁。


相关文章