本文主要是介绍小白月赛91E Bingbong的字符串世界，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
知识点：系列自动机
刚开始想偏了，直接在字符串上操作，导致漏算了一些字符，ACCEPT前后都可以有字符串。
所以参考b站的讲解，要使用一个二维数组记录从i位开始第一次出现某字母的位置（某字母指26个大写字母），这样才会在不漏任何一个符合条件的字符串
从n开始的目的是为了排除从此位置开始那些没出现的字母
inline void count(){for(int i=n;i>=0;i--){for(int j=0;j<26;j++){if(i==n) nxt[i][j]=n;else nxt[i][j]=nxt[i+1][j];} nxt[i][s[i]-'A']=i; }
}寻找函数，x+1是因为有两个C，找完就返回位置
inline int find(int x,string &s){int first=1;for(auto ch:s){if(first) x=nxt[x][ch-'A'];else x=nxt[x+1][ch-'A'];first=0;if(x==n) return x;}return x;
}还有一个重要的点就是要考虑最短字符串长度k，所以要比较r1和i+k-1(i为起始位置)的大小
ACcode
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
typedef pair<int,int>PII;
#define rep(i,l,r) for(int i=l;i<r;i++)
const int N=2e5+10;
int n,k;
string s;
int nxt[N][30];
ll ans;inline int find(int x,string &s){int first=1;for(auto ch:s){if(first) x=nxt[x][ch-'A'];else x=nxt[x+1][ch-'A'];first=0;if(x==n) return x;}return x;
}inline void count(){for(int i=n;i>=0;i--){for(int j=0;j<26;j++){if(i==n) nxt[i][j]=n;else nxt[i][j]=nxt[i+1][j];} nxt[i][s[i]-'A']=i; }
}inline void solve(){cin>>n>>k>>s;count();string ac="ACCEPT",wa="WA";for(int i=0;i<n;i++){int r1=find(i,ac),r2=find(i,wa);if(r1==n) continue;r1=max(r1,i+k-1);ans+=(ll)max(r2-r1,0);}cout<<ans<<endl;
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);solve();return 0;
}这篇关于小白月赛91E Bingbong的字符串世界的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
