题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4259
题意:给出模式串和文本串,有通配符,问模式串在文本串的哪些位置出现了多少次。
同 两个串 ...
不同点在于需要再乘一个文本串,因为文本串也有通配符了... 另外貌似此题有点小卡空间?....
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 300010 #define MAXN 2000010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct cp { double x,y; cp(double X=0,double Y=0) { x=X,y=Y; } }x[MAXN],y[MAXN],ans[MAXN]; cp operator + (cp a,cp b){return cp(a.x+b.x,a.y+b.y);} cp operator - (cp a,cp b){return cp(a.x-b.x,a.y-b.y);} cp operator * (cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} int m,n,lena,lenb; char a[N],b[N]; int s[MAXN],t[MAXN],r[MAXN],L,q[N],top; void fft(cp *a,int n,int flag) { for(int i=0;i<n;i++) if(r[i]>i)swap(a[i],a[r[i]]); for(int i=1;i<n;i<<=1) { cp w_n(cos(M_PI/i),flag*sin(M_PI/i)); for(int j=0;j<n;j+=i<<1) { cp w(1,0); for(int k=0;k<i;k++) { cp x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y,a[j+k+i]=x-y; w=w*w_n; } } } } int main() { m=read(),n=read(); lena=n,lenb=m; scanf("%s%s",a,b); for(int i=0;i<n;i++) t[i]=b[i]=='*'?0:b[i]-'a'+1; for(int i=0;i<m;i++) s[m-i-1]=a[i]=='*'?0:a[i]-'a'+1; m=n+m; for(n=1;n<=m;n<<=1)L++; for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1)); for(int i=0;i<n;i++) x[i]=cp(s[i]*s[i]*s[i],0); for(int i=0;i<n;i++) y[i]=cp(t[i],0); fft(x,n,1),fft(y,n,1); for(int i=0;i<n;i++) ans[i]=x[i]*y[i]; for(int i=0;i<n;i++) x[i]=cp(s[i]*s[i],0); for(int i=0;i<n;i++) y[i]=cp(2*t[i]*t[i],0); fft(x,n,1),fft(y,n,1); for(int i=0;i<n;i++) ans[i]=ans[i]-x[i]*y[i]; for(int i=0;i<n;i++) x[i]=cp(s[i],0); for(int i=0;i<n;i++) y[i]=cp(t[i]*t[i]*t[i],0); fft(x,n,1),fft(y,n,1); for(int i=0;i<n;i++) ans[i]=ans[i]+x[i]*y[i]; fft(ans,n,-1); for(int i=0;i<n;i++) ans[i].x/=n; for(int i=0;i<=lena-lenb;i++) if(ans[i+lenb-1].x<0.5) q[++top]=i+1; printf("%d\n",top); for(int i=1;i<=top;i++) printf("%d ",q[i]); } /* 3 7 a*b aebr*ob */ |
Comments | NOTHING