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

文章目录

$Result$$Hyperlink$$Description$$Solution$$Code$

$Result$

---

$Hyperlink$

https://ac.nowcoder.com/acm/contest/7607/C

---

$Description$

有$n$组询问，每次给出一个$t$，再给定一个无限长的字符串，它的循环节是$s$，试求这个串的一个最短前缀$s^{‘}$，使得$t$是$s^{‘}$的一个子序列。其中$t$的某些位置可能是一个星号，表示这个位置可以是任意字符。

数据范围：$|s|\le 10^4,t\text{的真正长度}\le 10^{10^5}$

---

$Solution$

设$to{t}_i$表示原串中某个字符的个数，$q{z}_{i,j}$表示$s$的前$i$位，$j$字符的出现次数 $appea{r}_{i,j}$表示$s$串中$i$字符第$j$次出现的位置

考虑计算循环了几个$s$——$xh$ 考虑循环后需要某个字符多少个——$need$（当$s{t}_i\ne$星号时，这个字符就是$s{t}_i$，否则这个字符可以是任意字符） 考虑上次循环的结束位置——$last$ 对于输入的数很大的话，要用类似于高精度的方法对其进行处理

最后统计答案即可 时间复杂度：$O(26|s|+n|t|)$

---

$Code$

#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define mod 998244353 using namespace std;char s[10010],st[100010],ybd; int len,n,appear[26+150][10010]; LL xh,need,tot[26+150],qz[10010][26+150],once,ans,last; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline LL ksm(LL x,LL y) { LL res=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (res*=x)%=mod; return res; } inline bool tp() { for(register int i=1;i<=strlen(st+1);i++) if(st[i]!='*'&&!isdigit(st[i])&&tot[st[i]]==0) return true; return false; } signed main() { scanf("%s",s+1);len=strlen(s+1);s[len+1]=s[1]; for(register int i=1;i<=len;i++) { tot[s[i]]++; memcpy(qz[i],qz[i-1],sizeof(qz[i-1])); appear[s[i]][++appear[s[i]][0]]=i; qz[i][s[i]]++; } n=read(); while(n--) { scanf("%s",st+1); if(tp()) {puts("-1");continue;} ans=0;last=1; for(register int i=1;i<=strlen(st+1);i++) { ybd=st[i]; once=st[i]=='*'?len:tot[st[i]]; xh=0;need=0; if(isdigit(st[i+1])) { while(isdigit(st[i+1])) { xh=((xh<<3)+(xh<<1))%mod; need=((need<<3)+(need<<1)+st[++i]-48)%mod; (xh+=need/once)%=mod;need%=once; } } else need=1; if(ybd=='*') need+=once-(len-last+1);//加上上次做完后剩下的部分 else need+=once-(tot[ybd]-qz[last-1][ybd]);//同理 if(need>once) need-=once,xh++;//超过了一次，则构成一个循环 if(xh==0) xh=mod;//没有循环，直接让它＝mod if(need==0) need+=once,xh--;//不需要字符，则让它加上一次慢的，同时令循环少1 if(ybd!='*')//不是星号 { ans+=appear[ybd][need]-last+1;//补齐上次的 last=appear[ybd][need]%len+1;//同理 } else//是星号的话，则任意字符都可以 { ans+=need-last+1; last=need%len+1; } (ans+=len*xh%mod)%=mod;//加上循环的贡献 } printf("%lld\n",ans); } }