Time Limit:?20 Sec??Memory Limit:?256 MB
Submit:?398??Solved:?190

Description

兔子們在玩兩個串的游戲。給定兩個字符串S和T，兔子們想知道T在S中出現了幾次， 分別在哪些位置出現。注意T中可能有“?”字符，這個字符可以匹配任何字符。

?

Input

兩行兩個字符串，分別代表S和T

?

Output

第一行一個正整數k，表示T在S中出現了幾次 接下來k行正整數，分別代表T每次在S中出現的開始位置。按照從小到大的順序輸出，S下標從0開始。

?

Sample Input

bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab
a?aba?abba

Sample Output

0

HINT

?

S 長度不超過 10^5， T 長度不會超過 S。 S 中只包含小寫字母， T中只包含小寫字母和“?”

Source

?

數學 FFT 字符串 腦洞題

?

通配符的出現使得自動機失去了用武之地。DP雖然還能得出正確的結果，但是卻要跑一年。

盟軍急需找到新的匹配手段（霧）

?

如何判斷兩個字符相等？它們的編碼相等時它們就相等了(廢話)

如何判斷兩個字符串相等？它們對應每一位的編碼都相等時它們就相等了(廢話)

a=b有什么性質？a-b=0 (廢話)

那么兩個字符串相等時有Σ(a[i]-b[i])=0 ?(誒？)

當然Σ(a[i]-b[i])=0不一定代表兩串相等，可能前面多了一點，后面少了一點，加起來為0。

平方！?Σ((a[i]-b[i])^2)==0，沒有漏洞了。

那么我們得到一種新的匹配方式，它比起舊匹配方式……不但沒有優化，還多了平方的操作。

但如果將b數組翻轉，似乎……可以求卷積！

激動地將式子展開，得到 Σa[i]*a[i] +?Σb[i]*b[i] -Σ 2*a[i]*b[i] ，分別求三部分的卷積并累加，如果最終結果為0，說明字符串匹配上了！

通配符怎么解決？設通配符的值為0，在上面多乘一個b[i]得到Σ( b[i]*(a[i]-b[i])^2)==0 (當b[i]==0或b[i]==a[i]時可以匹配)。

FFT求卷積(O(nlogn))，若結果的第i位是0，那么(i-len(b)+1)到i這一段可以匹配。

マジやばくねー

注意精度誤差。

?

還要注意數組重復利用時的初始化……前期代碼寫太亂各種WA，最后一氣之下從0到n全部重新覆蓋……

?

題目加強版：http://www.cnblogs.com/SilverNebula/p/6511348.html

　　↑這一版代碼比下面這個優化程度高很多

?

?

1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<complex> 9 using namespace std; 10 const double pi=acos(-1.0); 11 const int mxn=810010; 12 typedef complex<double>com; 13 int read(){ 14 int x=0,f=1;char ch=getchar(); 15 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 16 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 17 return x*f; 18 } 19 int rev[mxn]; 20 int n,l; 21 void FFT(com *a,int flag){ 22 int i,j,x; 23 for(i=0;i<n;i++) 24 if(rev[i]>i)swap(a[rev[i]],a[i]); 25 for(i=1;i<n;i<<=1){ 26 com wn(cos(pi/i),flag*sin(pi/i)); 27 for(j=0;j<n;j+=(i<<1)){ 28 com w(1,0); 29 for(int k=0;k<i;k++,w*=wn){ 30 com x=a[j+k],y=w*a[i+j+k]; 31 a[j+k]=x+y; 32 a[i+j+k]=x-y; 33 } 34 } 35 } 36 if(flag==-1)for(i=0;i<n;i++)a[i]/=n; 37 } 38 char s1[mxn],s2[mxn]; 39 double a[mxn],b[mxn]; 40 com c[mxn],d[mxn]; 41 com e[mxn],two; 42 int ans[mxn],cnt=0; 43 int main(){ 44 int i,j; 45 scanf("%s",s1); 46 scanf("%s",s2); 47 int len=strlen(s1); int l2=strlen(s2); 48 int m=len<<1; 49 for(n=1;n<m;n<<=1)l++; 50 for(i=0;i<n;i++){rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));} 51 // 52 reverse(s2,s2+l2); 53 for(i=0;i<len;i++)a[i]=s1[i]-'a'+1; 54 for(i=0;i<l2;i++)if(s2[i]=='?')b[i]=0;else b[i]=s2[i]-'a'+1; 55 // 56 for(i=0;i<n;i++)c[i]=com(b[i]*b[i]*b[i],0);//b^3 57 for(i=0;i<n;i++)d[i]=com(1,0); 58 FFT(c,1);FFT(d,1); 59 for(i=0;i<n;i++)e[i]=c[i]*d[i]; 60 for(i=0;i<n;i++)c[i]=com(a[i]*2,0); 61 for(i=0;i<n;i++)d[i]=com(b[i]*b[i],0); 62 FFT(c,1);FFT(d,1); 63 for(i=0;i<n;i++)e[i]-=c[i]*d[i]; 64 for(i=0;i<n;i++)c[i]=com(a[i]*a[i],0); 65 for(i=0;i<n;i++)d[i]=com(b[i],0); 66 FFT(c,1);FFT(d,1); 67 for(i=0;i<n;i++)e[i]+=c[i]*d[i]; 68 FFT(e,-1); 69 for(i=l2-1;i<len;i++){ 70 if(abs(e[i].real())<0.5){ 71 ans[++cnt]=i-l2+1; 72 } 73 } 74 printf("%d\n",cnt); 75 for(i=1;i<=cnt;i++){ 76 printf("%d\n",ans[i]); 77 } 78 return 0; 79 }

?

轉載于:https://www.cnblogs.com/SilverNebula/p/6511330.html

總結

以上是生活随笔為你收集整理的Bzoj4503 两个串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。