✨博主:命运之光 🦄专栏:算法修炼之练气篇 🍓专栏:算法修炼之筑基篇 ✨博主的其他文章:点击进入博主的主页 前言:学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期难度可谓是天差地别,懂得都懂,题目难度相比起练气期的题目难度提升很多,所以要是各位蒟蒻小伙伴们看不懂筑基期的题目可以在练气期多积累积累,练气期的题目也会不断更新,大家一定要把基础打牢固了再来看筑基期的题目哈,这样子也可以提高大家的学习效率,一举两得,加油(●'◡'●)🎉🎉
太经典的KMP算法妥妥的模板题,不会的直接背就行
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> buildNext(const string& pattern) {
int n = pattern.length();
vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1];
if (pattern[i] == pattern[j])
j++;
next[i] = j;
}
return next;
}
int findLongestPrefix(const string& s, const string& t) {
int sLen = s.length();
int tLen = t.length();
vector<int> next = buildNext(t);
int maxLen = 0;
int i = 0, j = 0;
while (i < sLen) {
if (s[i] == t[j]) {
i++;
j++;
maxLen = max(maxLen, j);
if (j == tLen)
break;
} else if (j > 0) {
j = next[j - 1];
} else {
i++;
}
}
return maxLen;
}
int main() {
string s, t;
cin >> s >> t;
int result = findLongestPrefix(s, t);
cout << result << endl;
return 0;
}
以上代码中的buildNext函数和findLongestPrefix函数都是KMP算法中的常见实现。其中,buildNext函数用于构建模式串T的部分匹配表(也称为next数组),而findLongestPrefix函数则使用双指针和next数组进行匹配,寻找T串的前缀在S串中出现的最长长度。
buildNext函数中的循环部分使用了KMP算法中的核心思想,根据当前位置的字符和已计算的next值来更新next数组。findLongestPrefix函数中的循环部分也使用了KMP算法的思想,通过根据next数组进行指针的移动和回溯来实现高效的字符串匹配。
以上代码可以被认为是KMP算法的一种实现模板。当需要在字符串中寻找模式串出现的位置或计算最长匹配长度时,可以基于这个模板进行相应的修改和使用。
改写上面的KMP算法,这道题依旧是一道经典的标准的KMP算法模板
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> buildNext(const string& pattern) {
int n = pattern.length();
vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1];
if (pattern[i] == pattern[j])
j++;
next[i] = j;
}
return next;
}
int countOccurrences(const string& s, const string& t) {
int sLen = s.length();
int tLen = t.length();
vector<int> next = buildNext(s);
int count = 0;
int i = 0, j = 0;
while (j < tLen) {
if (s[i] == t[j]) {
i++;
j++;
if (i == sLen) {
count++;
i = next[i - 1];
}
} else if (i > 0) {
i = next[i - 1];
} else {
j++;
}
}
return count;
}
int main() {
string s1, s2;
getline(cin, s1);
getline(cin, s2);
int result = countOccurrences(s1, s2);
cout << result << endl;
return 0;
}
太经典了,不理解KMP算法的直接背就行,理解KMP算法但每次写的时候都急忙写不出来的也直接背就行,写题时稍加修改即可,一道送分题,往往写不出来KMP就变成送命题了。
vector<int>被用于存储KMP算法中的部分匹配表(也称为next数组)。
具体来说,vector<int> buildNext(const string& pattern)函数的返回类型是vector<int>,它表示该函数会返回一个存储整数类型元素的动态数组。在这个函数中,我们使用vector<int> next(n, 0)来创建了一个长度为n的动态数组,初始值都为0。这里的n是模式串pattern的长度。
KMP算法中的部分匹配表(next数组)是一个整数数组,用于存储每个位置之前最长相同前缀后缀的长度。在构建next数组时,我们会逐步计算每个位置的值,并将其存储在vector<int>中。
例如,当输入模式串为"ABABCABD"时,构建的next数组为[0, 0, 1, 2, 0, 1, 2, 0]。在这个数组中,第i个元素表示模式串中以第i个字符结尾的子串的最长相同前缀后缀的长度。
在C++中,const string& s 和 const string& t 是函数参数的声明形式。
这种使用常量引用的方式,既能保证在函数内部不修改字符串的内容,又能避免不必要的字符串复制,提高效率。
在函数体内部,可以像使用普通字符串一样使用这些参数,例如使用 s.length() 获取字符串 s 的长度,使用 s[i] 访问字符串 s 的第 i 个字符。
这段代码实现了KMP算法中构建部分匹配表(next数组)的功能。下面对代码进行详细解释:
vector<int> buildNext(const string& pattern) {
int n = pattern.length(); // 获取模式串的长度
vector<int> next(n, 0); // 创建一个长度为n的动态数组next,并初始化为0
int j = 0; // 初始化匹配位置j为0
for (int i = 1; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1]; // 回溯到前一个匹配位置
if (pattern[i] == pattern[j])
j++; // 匹配成功,将j向后移动一位
next[i] = j; // 更新next数组的值
}
return next; // 返回构建好的next数组
}
🍓代码的执行流程如下:
最终,该函数返回的 next 数组即为模式串的部分匹配表(next数组),其中每个位置的值表示以当前位置结尾的子串的最长相同前缀后缀的长度。
这段代码实现了使用KMP算法计算字符串S1在字符串S2中出现次数的功能。下面对代码进行详细解释:
int countOccurrences(const string& s, const string& t) {
int sLen = s.length(); // 获取字符串S1的长度
int tLen = t.length(); // 获取字符串S2的长度
vector<int> next = buildNext(s); // 构建字符串S1的部分匹配表(next数组)
int count = 0; // 计数器,记录S1在S2中出现的次数
int i = 0, j = 0; // 双指针i和j,分别指向S1和S2的当前位置
while (j < tLen) {
if (s[i] == t[j]) { // 当S1的当前字符和S2的当前字符匹配时
i++;
j++;
if (i == sLen) { // 如果S1已经完全匹配,则找到了一个出现次数
count++;
i = next[i - 1]; // 回溯到S1的下一个可能的起始位置
}
} else if (i > 0) { // 当S1的当前字符和S2的当前字符不匹配时
i = next[i - 1]; // 回溯到S1的前一个匹配位置
} else {
j++; // 如果S1的第一个字符都不匹配,则继续在S2中向后移动
}
}
return count; // 返回S1在S2中出现的次数
}
🍓代码的执行流程如下:
这段代码是程序的入口点,也就是主函数 main()。下面对代码进行详细解释:
int main() {
string s1, s2;
getline(cin, s1); // 从输入中读取一行字符串,存储到变量 s1 中
getline(cin, s2); // 从输入中读取一行字符串,存储到变量 s2 中
int result = countOccurrences(s1, s2); // 调用 countOccurrences 函数计算字符串 s1 在字符串 s2 中出现的次数,并将结果存储在变量 result 中
cout << result << endl; // 输出结果
return 0; // 返回 0 表示程序正常结束
}
🍓代码的执行流程如下:
整个代码的作用是读取两行字符串作为输入,然后计算第一行字符串在第二行字符串中出现的次数,并将结果输出。
看到这里给我个人觉得经典的程序是需要记忆的,比赛直接就可以上手写,速度快。一定要记忆,这里我已经把所有的代码都解释了,帮助大家理解记忆这个经典的KMP算法,咱就一句话,虽然咱不是很理解KMP算法,但这妨碍咱竞赛秒杀KMP算法吗?不妨碍的,你说是吧(●'◡'●)🤭
#include <iostream>
#include <vector>
using namespace std;
vector<int> buildNext(const string& pattern) {
int n = pattern.length();
vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j])
j = next[j - 1];
if (pattern[i] == pattern[j])
j++;
next[i] = j;
}
return next;
}
int countOccurrences(const string& s, const string& t) {
int sLen = s.length();
int tLen = t.length();
vector<int> next = buildNext(s);
int count = 0;
int i = 0, j = 0;
while (j < tLen) {
if (s[i] == t[j]) {
i++;
j++;
if (i == sLen) {
count++;
i = next[i - 1];
}
} else if (i > 0) {
i = next[i - 1];
} else {
j++;
}
}
return count;
}
int main() {
string s, t;
getline(cin, s);
getline(cin, t);
int result = countOccurrences(s, t);
cout << result << endl;
return 0;
}
🦄可以发现这个就是上面第二题一样的解法,毕竟第二题就是模板,第一题也是,记就完事了。