目录
- 一、暴力匹配法
- 动画演示
- 代码实现
- 二、KMP算法的概念
- 三、KMP算法的应用
- 题目
- 代码实现
一、暴力匹配法
动画演示
时间复杂度为: O ( m ∗ n ) O(m * n) O(m∗n)
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;int find(string& s1, string& s2)
{int n = s1.size();int m = s2.size();for (int i = 0; i <= n - m; ++i){int cp = i, j = 0;while (cp < n && s1[cp] == s2[j]) cp++, j++;if (j == m - 1) return cp;}return -1;
}
int main()
{string txt = "ABCDABCDABDE";string pat = "ABCDABD";cout << find(txt, pat) << endl;return 0;
}
二、KMP算法的概念
K M P KMP KMP 算法,通常用于在一个 文本字符串 S S S 中查找一个 匹配串 P P P 的 出现位置 和 出现次数。
KMP算法首先对模式串进行预处理,计算出Next数组。Next数组的每个元素表示当前位置之前的子串中,最长的相等的前缀和后缀的长度。然后,在匹配过程中,使用Next数组来指导模式串的移动。
当模式串与文本串的某个字符不匹配时,根据Next数组的值确定模式串的移动位置,而不是从头开始逐个字符地比较。通过合理地利用Next数组,KMP算法能够有效地避免不必要的比较操作,从而提高匹配的效率。
难点在于通过预处理得到Next数组 及其 回退处理的操作
相关求解视频:
【搬运】油管阿三哥讲KMP查找算法,中英文字幕,人工翻译,简单易懂
三、KMP算法的应用
题目
题目描述:
给定一个字符串 S S S,以及一个模式串 P P P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P P P 在字符串 S S S 中多次作为子串出现。
求出模式串 P P P 在字符串 S S S 中所有出现的位置的起始下标。
输入格式:
第一行,输入整数 n n n,表示字符串 P P P 的长度。
第二行,输入字符串 P P P。
第三行,输入整数 m m m,表示字符串 S S S 的长度。
第四行,输入字符串 S S S。
输出格式:
共一行,输出所有出现位置的起始下标(下标从 0 0 0 开始计数),整数之间用空格隔开。
数据范围:
1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105
1 ≤ m ≤ 1 0 6 1≤m≤10^6 1≤m≤106
输入样例:
3
aba
5
ababa
输出样例:
0 2
代码实现
const int N = 1e5 + 10, M = 1e6 + 10;int ne[N];
char s[M];
char p[N];int main()
{cin.tie(nullptr);int n, m;cin >> n;for (int i = 0; i < n; ++i) cin >> p[i];cin >> m;for (int i = 0; i < m; ++i) cin >> s[i];// 创建Next数组// i:当前试图进行匹配的S串字符,j是模板串当前试图与S串i位置进行匹配的字符// j:表示已匹配的长度,一直都在尝试让j位和i位进行匹配,退无可退,无需再退。// i:是从1开始的,因为ne[0]=0,表示第1个不匹配,只能重头开始,不用算for (int i = 1, j = 0; i < n; i++) // j - 前缀末,i - 后缀末{while (j && p[i] != p[j]) j = ne[j - 1];if (p[i] == p[j]) j++;ne[i] = j;}for (int i = 0, j = 0; i < m; i++){while (j && s[i] != p[j]) j = ne[j - 1];if (s[i] == p[j]) j++;if (j && j == n){printf("%d ", i + 1 - n);j = ne[j - 1];}}return 0;
}