歸途與征程 Journey

2019-11-11 02:02:14

字體：大中小

來源：轉載

供稿：網友

歸途與征程

(journey.pas/c/cpp)

題目描述

“感謝你們來訪 Nescafe 之塔，封印的能量會在兩天之內完全被貯存在神杯之中，你們也該回去了。” “不過圣主，我們還有一個問題。難道……Nescafe 就這樣被封印成一座神杯，保存在塔中了嗎？” “也許吧。誰知道呢？或許來年的秋天會有有識之士來開啟它呢……” “有識之士？他是誰？” “如果有這樣幾個人，那他們一定來自忘川滄月家族的 10 個孩子！他們……也該踏上征程了……” “是這樣……祝福他們吧……圣主您多保重，我們探險隊要走了。” “一路平安……不過走之前我還給你們留了一份紀念品呢~” “紀念品？這是~!@#$%^&*()_+……一道題！” 給出一個長度為 N 的由小寫字母’a’~’z’和’’組成的字符串 A，一個長度為 M 的僅由小寫字母’a’~’z’組成的字符串 B。一個’’可以匹配任意多個字符（包括 0 個）。求在 B 的所有循環同構串中，有多少個能夠與 A 匹配。循環同構串：就是把 B 的前 k 個字母(0<=k<M $0<=k<M$ )移到結尾所得到的字符串。例如 abc 的循環同構串有 abc、bca 和 cab。 A 與 B 匹配：若除了 A 中的’? $*$ ’號可以匹配 B 中的任意多個字符外，其余字符一一對應，則稱 A 與 B 匹配。例如 a?b?c $a*b*c$ 與 aadbc 是匹配的，其中第一個? $*$ 對應 ad，第二個? $*$ 對應空串。

輸入格式

第一行為字符串 A。第二行為字符串 B。輸出格式輸出在 B 的所有循環同構串中，有多少個能夠與 A 匹配。

樣例輸入 1

aaaa aaaa

樣例輸出 1

樣例輸入 2

a?a $a*a$ aaaaaa $aaaaaa$

樣例輸出 2

樣例輸入 3

?a?b?c? $*a*b*c*$ abacabadabacaba $abacabadabacaba$

樣例輸出 3

數據范圍與約定

對于 30% 的測試點，M≤20。對于 80% 的測試點，M≤200。對于 100% 的測試點，1<=N<=100，1≤M≤100000。

正解思路：把b串復制一下，kmp搞一搞

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=110,M=200010;int n,m,len,num,next[N],f[N][M];//表示第j個位置及其右邊的第一個能與A串的i小串相匹配的位置int c[N];//c:每一個匹配串的長度 char a[N],b[M];char s[N];//當前匹配串的長度 bool p1,pn;//第一個最后一個是否為* bool bz[N][M];//表示第i個小串是否能與B的第j個位置往后相應長度匹配void kmp(int st)//start{ int j=0; for(int i=2;i<=n;i++)//next { while(j && s[i]!=s[j+1]) j=next[j]; next[i]=s[i]==s[j+1]?(++j):(j=0); } j=0; for(int i=2;i<=m*2;i++)//bz { while(j && b[i]!=s[j+1]) j=next[j]; if(b[i]==s[j+1]) j++; if(j==c[st]) bz[st][i-j+1]=1; } f[st][m*2+1]=m*2+1; for(int j=m*2;j>=1;j--)//f if(bz[st][j]) f[st][j]=j; else f[st][j]=f[st][j+1];}bool match(int x){ int y=x+m-1,l=1,r=num; if(!p1) { if(!bz[l][x]) return 0; x+=c[l++]; } if(!pn) { if(!bz[r][y-c[r]+1]) return 0; y-=c[r--]; } for(;l<=r;l++) { x=f[l][x]; if(x>y) return 0; x+=c[l]-1; } if(x>y) return 0; return 1;}int main(){ freopen("journey.in","r",stdin); freopen("journey.out","w",stdout); scanf("%s/n%s",a+1,b+1); n=strlen(a+1),m=strlen(b+1); p1=a[1]=='*',pn=a[n]=='*'; for(int i=m+1;i<=m*2;i++) b[i]=b[i-m]; for(int i=1;i<=n;i++) { int len=0; for(;i<=n && a[i]!='*';i++) s[++len]=a[i]; if(!len) continue; c[++num]=len; kmp(num); } int ans=0; for(int i=1;i<=m;i++) if(match(i)) ans++;