归途与征程 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++; PRintf("%d/n",ans); return 0;}

上一篇：tomcat 启动报错 org.apache.catalina.deploy.WebXml addFilter 解决

下一篇：使用gdbserver+arm-linux-gdb 调试应用程序