首页 > 代码库 > Bzoj4259 残缺的字符串

Bzoj4259 残缺的字符串

2024-09-07 03:52:42   216人阅读

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 387  Solved: 93

Description

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串A和B，其中A串长度为m，B串长度为n。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。
你想对这两个串重新进行匹配，其中A为模板串，那么现在问题来了，请回答，对于B的每一个位置i，从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?
 

 

Input

第一行包含两个正整数m,n(1<=m<=n<=300000)，分别表示A串和B串的长度。
第二行为一个长度为m的字符串A。
第三行为一个长度为n的字符串B。
两个串均仅由小写字母和*号组成，其中*号表示相应位置已经残缺。
 

 

Output

第一行包含一个整数k，表示B串中可以完全匹配A串的位置个数。
若k>0，则第二行输出k个正整数，从小到大依次输出每个可以匹配的开头位置（下标从1开始）。
 

 

Sample Input

3 7
a*b
aebr*ob

Sample Output

2
1 5

HINT

 

Source

By Claris

 

数学问题 FFT 字符串 脑洞题

题解看这里→ http://www.cnblogs.com/SilverNebula/p/6511330.html

这道题只不过给两个串都加了通配符而已。只要在之前那道题的式子上再乘一个a[i]就可以了。

 

跑得巨慢，尝试优化各种地方，在submission status上留下了一串红。

最后发现我的FFT板子之前是用来处理等长卷积的，所以长度直接设成len*2，实际上只用len(a)+len(b)就可以了(第43行)

速度快了一倍，4768ms成功rank7

↑在此之前手写复数类从1w+优化9000ms

 

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const double pi=acos(-1.0);10 const int mxn=1150011;11 struct com{12     double a,b;13     com operator + (const com y){return (com){a+y.a,b+y.b};}14     com operator - (const com y){return (com){a-y.a,b-y.b};}15     com operator * (const com y){return (com){a*y.a-b*y.b,a*y.b+b*y.a};}16 }c[mxn],d[mxn],e[mxn];17 double a[mxn],b[mxn];18 int n,l;19 int rev[mxn];20 void FFT(com *a,int flag){21     int i,j,k;22     for(i=0;i<n;i++){if(rev[i]>i)swap(a[rev[i]],a[i]);}23     for(i=1;i<n;i<<=1){24         com wn=(com){cos(pi/i),flag*sin(pi/i)};25         for(j=0;j<n;j+=(i<<1)){26             com w=(com){1,0};27             for(k=0;k<i;k++,w=w*wn){28                 com x=a[j+k],y=w*a[i+j+k];29                 a[j+k]=x+y;30                 a[i+j+k]=x-y;31             }32         }33     }34     if(flag==-1)for(i=0;i<n;i++)a[i].a/=n;35 }36 char s1[300021],s2[300021];37 int ans[mxn],cnt=0;38 int main(){39     int l1,l2;40     scanf("%d%d",&l2,&l1);41     int i,j;42     scanf("%s",s2);scanf("%s",s1);43     int m=l1+l2;44     for(n=1;n<m;n<<=1)l++;45     for(i=0;i<n;i++){rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));}46     for(i=0;i<l1;i++){47         if(s1[i]!=‘*‘)a[i]=s1[i]-‘a‘+1;48         else a[i]=0;49     }50     for(i=0;i<l2;i++){51         if(s2[i]!=‘*‘)b[l2-i-1]=s2[i]-‘a‘+1;52         else b[l2-i-1]=0;53     }54     for(i=0;i<l1;i++){55         c[i].a=a[i]*a[i]*a[i];56     }57     for(i=0;i<l2;i++){58         d[i].a=b[i];59     }60     FFT(c,1);FFT(d,1);61     for(i=0;i<n;i++){e[i]=c[i]*d[i];}//a^3*b62     //63 //    memset(c,0,sizeof c);64 //    memset(d,0,sizeof d);65     for(i=0;i<n;i++){c[i].a=a[i]*a[i];c[i].b=0;}66     for(i=0;i<n;i++){d[i].a=b[i]*b[i];d[i].b=0;}67     FFT(c,1);FFT(d,1);68     com tmp=(com){2,0};69     for(i=0;i<n;i++){e[i]=e[i]-c[i]*d[i]*tmp;}//2ab*a*b70     //71 //    memset(c,0,sizeof c);72 //    memset(d,0,sizeof d);73     for(i=0;i<n;i++){c[i].a=a[i];c[i].b=0;}74     for(i=0;i<n;i++){d[i].a=b[i]*b[i]*b[i];d[i].b=0;}75     FFT(c,1);FFT(d,1);76     for(i=0;i<n;i++){e[i]=e[i]+c[i]*d[i];}//b^3*a77     //78     FFT(e,-1);79     for(i=l2-1;i<l1;i++)80         if(abs(e[i].a)<=0.5){81             ans[++cnt]=i-l2+2;82         }83     printf("%d\n",cnt);84     for(i=1;i<=cnt;i++){85         printf("%d ",ans[i]);86     }87     return 0;88 }

 

Bzoj4259 残缺的字符串


联系
我们