Educational Codeforces Round 178 (Rated for Div. 2)E. Unpleasant Strings

题目链接

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
typedef pair<int,int>PII;
typedef priority_queue<int> upq;
typedef priority_queue<int,vector<int>,greater<int>> dpq;
const int M=998244353;
const int N=1e6+20;
//1.快速知道字符串t是s的前几个字符的子序列
//2.从s的第i个字符开始，还需要加几个字符，可以使i跳到n+1//next_id[i][j]:第i个字符之后的第一个字符j的出现位置
//dp[i]：若前i个字符与字符串已经完全匹配，则还需要增加几个字符
int nxt_id[N][27],dp[N];
int lst[N]; 
char a[N];
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,k; cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;i<N;i++) dp[i]=1e9+5; for(int i=0;i<k;i++) nxt_id[n+1][i]=n+1,lst[i]=n+1;dp[n+1]=0;for(int i=n;i>=0;i--){for(int j=0;j<k;j++){nxt_id[i][j]=lst[j];dp[i]=min(dp[i],dp[nxt_id[i][j]]+1);}if(i!=0) lst[a[i]-'a']=i;}int q; cin>>q;while(q--){string t; cin>>t;int id=0;for(int i=0;i<t.size();i++){id=nxt_id[id][t[i]-'a'];}cout<<dp[id]<<"\n";}
}