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" 的起始位置并存入集合 st
        for (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
            }
        }
    }
}