字符串算法

1.kmp匹配算法

模板题链接
不懂可以看这个~详细的思路

#include <string>
#include <iostream>using namespace std;
const int N = 1000010;string s,p;// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
int ne[N];int main()
{//读取字符串并在揩油加一个空格,使下标从1开始 cin >> s >> p;s = " " + s; p = " " + p; int n = s.size() - 1; //s的有效长度 int m = p.size() - 1;//p的有效长度 //求next数组 for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=ne[j];// 从j位置回退if(p[i]==p[j+1])j++;// 如果匹配，j++ne[i]=j;// 保存最长前后缀的长度} //匹配操作 for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1])j=ne[j]; // 从j位置回退if(s[i]==p[j+1])j++; // 如果匹配，j++if(j==m)// 完全匹配{//匹配完成后的具体操作//如：输出以0开始的匹配子串的首字母下标//cout<<i-m<<endl;//如：输出以0开始的匹配子串的首字母下标//cout<<i-m+1<<endl; j=ne[j];// 根据 ne 数组更新 j}}for(int i=1;i<=m;i++){cout<<ne[i]<<' ';//输出next数组,也就是输出前缀的最长 border 长度。 }return 0;
}

Anya and 1100

传送门

#include <bits/stdc++.h> 
using namespace std;int main() {ios_base::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { string s; cin >> s; set<int> st; // 使用集合来存储 "1100" 出现的起始位置int n = (int) s.size(); // 遍历字符串 s，找到所有 "1100" 的起始位置并存入集合 stfor (int i = 0; i < (int) s.size()-3; i++) {if (s.substr(i, 4) == "1100") st.insert(i); // 将起始位置插入集合}int q; cin >> q; while (q--) { int i; char v; cin >> i >> v; if (n < 4) { // 如果字符串长度小于 4，无法形成 "1100"cout << "NO\n"; continue; }i--; // 转换为 0 基索引if (s[i] != v) { // 如果 s[i] 的值与新值 v 不同// 更新之前，删除对 "1100" 出现情况的影响for (int j = max(0, i-3); j <= i; j++) {if (s.substr(j, 4) == "1100") // 检查子串st.erase(j); // 如果找到了，移除集合中的位置}s[i] = v; // 更新字符串中的字符// 更新之后，重新检查 "1100" 的出现情况for (int j = max(0, i-3); j <= i; j++) {if (s.substr(j, 4) == "1100") // 检查子串st.insert(j); // 如果找到了，添加到集合中}}// 根据集合 st 的情况输出结果if (st.empty()) {cout << "NO\n"; // 如果集合为空，输出 NO}else {cout << "YES\n"; // 否则输出 YES}}}
}