2020牛客NOIP赛前集训营-提高组（第二场）C前缀

题目

传送门

题目描述

牛牛有一个$s$串,$s$串仅由$26$个小写英文字母组成，他现在将$s$串进行了无限次的复制扩展成了一个无限循环串。 例如一开始$s=“abc”$，那么牛牛就会将其变为$“abcabcabc...”$ 若某个字符串保留其原本字符出现的顺序，并且按照顺序取出若干个字符。可以不连续，可以不取。 我们称取出的这若干个字符连成的字符串为一个子序列。 若连续取出某个字符串的前$k$个字符，组成一个子串，我们称该字符串为原串长度为$k$的前缀。 对于一个字符串$t$，若某字符串的至少一个子序列为$t$。则称它是一个$“$含$t$序列串$”$ 牛牛想要知道对于给定的t，他想要知道s的一个最短前缀满足它是一个$“$含$t$序列串$”$，它的长度有多长？ 由于答案可能非常大，所以他要求你输出答案对$998244353$取余数后的结果即可。 特别的，如果$S$串不存在任何一个前缀满足他是一个$“$含$t$序列串$”$，请输出$“-1”$表示无解。 $t$串中除了$26$个英文字母以外还会出现$“\ast ”$，表示一个通配符。统配符可以视为任意字母。 例如循环$s$串为$“abcabcabcabc..."$，$t$串为$“a\ast ca”$时，最短含$t$序列前缀长$4$。而当$t$串为$“a\ast \ast ca”$时，最短含t序列前缀长$7$。 除此之外，牛牛输入的$t$串还可能非常非常长，最长可以达到$10^{10^5}$这么长。 所以他想了一种压缩方法，来快速读入$t$串。 具体来说，它输入的$t$串中除了$“\ast ”$和$26$个小写英文字母以外，还会跟有一些正整数。 在读入字符串时，这些数字表示它前面字母或者"*"重复的次数。 例如$a5bc\ast 3$，表示$“aaaaabc\ast \ast \ast ”$。输入的正整数不含前导0。

输入描述

第一行输入一个仅包含$26$个小写英文字母的字符串$s$ 第二行输入一个正整数$n$表示，$t$串的数目。 接下来输入$n$行 再输入一行一个字符串$t$，表示压缩后的查询串。查询串仅包含$26$个小写英文字母，星号${}^{\prime }{\ast }^{\prime }$，以及数字。

输出描述

对于每一个查询，如果至少存在一个$s$的前缀满足$“$最短含$t$序列串$”$的定义，请输出$s$的最短含$t$序列前缀的长度对$998244353$取余数后的结果。 否则请输出$“-1”$表示无解。

分析

本题采用一种叫$“$序列自动机$”$的玄学操作进行初始化：

for(i=1;i<=n;i++) { for(j=0;j<27;j++) s[j][i]=s[j][i-1]; ++s[T[i]-'a'+1][i],++s[0][i]; }

其中$j$表示字符（$0$表示$\ast$），$i$表示当前序列元素的下标，$s[j][i]$表示在第$i$位之前出现了$s[j][i]$个$j$ 这样初始化完了之后，我们模拟一下，就快乐AC！

#include <bits/stdc++.h> using namespace std; const int N=100012,mod=998244353; int n,m,i,j,l,r,q,v,rem,now,x,res,ne,s[27][N],ans=0;char T[N];bool fl; int ABS(int x){if(x>=mod) return x-mod; if(x<0) return x+mod; return x;} int main() { scanf("%s %d",T+1,&q),n=strlen(T+1); for(i=1;i<=n;i++) { for(j=0;j<27;j++) s[j][i]=s[j][i-1]; ++s[T[i]-'a'+1][i],++s[0][i]; }//序列自动机 while(q--) { scanf("%s",T+1),m=strlen(T+1),ans=0,now=1,fl=1; for(i=1;i<=m;i=r+1) { v=(T[i]=='*') ? 0:(T[i]-'a'+1); if(!s[v][n]){fl=0;break;}r=i,rem=1,res=0; if(i+1<=m&&T[i+1]>='0'&&T[i+1]<='9') { rem=0,l=i+1; while(r+1<=m&&T[r+1]>='0'&&T[r+1]<='9') ++r; x=s[v][n]; for(i=l;i<=r;i++) rem=rem*10+(T[i]-'0'),res=(10ll*res+rem/x)%mod,rem%=x;//大数除法 res=1ll*res*n%mod; if(!rem) rem=x,res=ABS(res-n); }//处理数字并顺带取模 if(s[v][n]-s[v][now-1]<rem) res=ABS(res+n-now+1),rem-=s[v][n]-s[v][now-1],now=1; ne=lower_bound(s[v]+now,s[v]+n+1,s[v][now-1]+rem)-s[v]+1; res=ABS(res+ne-now),now=ne,ans=ABS(ans+res); } if(fl) printf("%d\n",ans); else puts("-1"); } }

----原创文章，仅供参考