loj2576 「TJOI2018」str

link

题意：

给一个模板串s和n个模式串，每个模式串有$a_i$种可取的串。现在要将n个模式串每个任取一种它可取的串，连接起来，记为串t，那么这种连接方式对答案的贡献为t在s中出现的次数。问所有连接方式的贡献之和。

$n\leq 100,|S|\leq 10^4.$

题解：

设f[i][j]表示使用前i个模式串，匹配前j位的贡献。对每个模式串的每种可能转移，使用hash判断是否匹配。

复杂度$\mathcal{O}(|S|\times \sum a_i)$。

花絮：

今天我生日> <，生快啦。

code：

 #include<bits/stdc++.h>

 #define rep(i,x,y) for (int i=(x);i<=(y);i++)

 #define ll long long

 #define inf 1000000001

 #define y1 y1___

 using namespace std;

 char gc(){

     static char buf[],*p1=buf,*p2=buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

 }

 #define gc getchar

 ll read(){

     char ch=gc();ll x=;int op=;

     for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-;

     for (;isdigit(ch);ch=gc()) x=(x<<)+(x<<)+ch-'';

     return x*op;

 }

 #define N 10005

 #define M 105

 #define mod 1000000007

 #define seed 233

 #define happy_birthday 20180731

 int n,m,now,f[][N],h[N],pw[N],ans;//f[i][j]：使用前i个字符串，匹配前j位的匹配方案数

 char str[N],s[N];

 void upd(int &x,int y){x+=y;x-=x>=mod?mod:;}

 void init(){

     h[]=;pw[]=;

     rep (i,,n){

         h[i]=((ll)h[i-]*seed+str[i])%happy_birthday;

         pw[i]=(ll)pw[i-]*seed%happy_birthday;

     }

 }

 int cal(int x,int y){

     return (h[y]+happy_birthday-(ll)h[x-]*pw[y-x+]%happy_birthday)%happy_birthday;

 }

 int main(){

     m=read();

     scanf("%s",str+);n=strlen(str+);

     init();

     now=;rep (i,,n) f[][i]=;//可以从任意位置开始

     while (m--){

         now^=;memset(f[now],,sizeof(f[now]));

         for (int k=read();k;k--){

             scanf("%s",s+);int l=strlen(s+);

             int hsh=;rep (i,,l) hsh=((ll)hsh*seed+s[i])%happy_birthday;

             rep (i,,n-l+)

                 if (cal(i,i+l-)==hsh) upd(f[now][i+l-],f[now^][i-]);

         }

     }

     rep (i,,n) upd(ans,f[now][i]);

     printf("%d\n",ans);

     return ;

 }

巴特西

loj2576 「TJOI2018」str

题意：

题解：

花絮：

code：

最新文章

热门文章