前缀和匹配

传送门
给出一个字符串，然后匹配子字符串
子字符串可以是非连续的，但字典顺序要一致

匹配子字符串为abc

/*
类似前缀和
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
string s;
int main(){
    cin>>s;
    ll a=0,b=0,c=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='a')a++;
        if(s[i]=='b')b+=a;
        if(s[i]=='c')c+=b;
    }
    cout<<c<<endl;
    return 0;
}

匹配子字符串是否出现

传送门
好吧，很水的模板

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,q,i,pos,f;
string s,a;//主串s,子串a
int main(){
    cin>>n>>q>>s;
    while(q--){
        cin>>a,pos=0,f=1;
        for(i=0;i<a.length()&&f;i++){//遍历子串的所有字母
            auto it=s.find(a[i],pos);//在主串中找子串的字母第一次出现的位置,pos表示从pos开始寻找
            //printf("%d\n",it);
            if(it==s.npos)f=0;//npos表示不存在
            else pos=it+1;
        }
        puts(f?"YES":"NO");
    }
}

前缀和匹配

原文：https://www.cnblogs.com/Emcikem/p/11480516.html