Main » 2013 October 10 » 终于A了「Poetize10」归途与征程
11:29 AM 终于A了「Poetize10」归途与征程 |
RKhash#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<vector> #include<set> #include<map> #include<string> #include<algorithm> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define pb push_back #define mp make_pair #define N 200010 #define M 61 #define PRIME 13331 using namespace std; typedef unsigned long long ULL; typedef long double LD; char a[N],b[N]; ULL c[N],p[N],g[2*M],tmp; int f[N][M],len[N]; ULL F(char cc){return cc-'a'+1;}; int main() { scanf("%s",a+1); scanf("%s",b+1); int i,j; int n=strlen(a+1),m=strlen(b+1); FOR(i,1,m) b[i+m]=b[i]; p[0]=1; FOR(i,1,n) p[i]=p[i-1]*PRIME; int L=0;j=0; FOR(i,1,n) if (a[i]=='*') { if (i>1&&a[i-1]!='*') {c[++L]=tmp;len[L]=j;tmp=j=0;}} else tmp+=F(a[i])*p[j++]; if (a[n]!='*') {c[++L]=tmp;len[L]=j;tmp=j=0;} if (!L) {printf("%d\n",m);return 0;} FOR(i,1,L) f[2*m+1][i]=f[2*m+2][i]=2*m+1; ROF(i,2*m,1) { memset(g,-1,sizeof(g)); g[0]=0; FOR(j,0,n-1) if (i+j<=2*m) g[j+1]=g[j]+(b[i+j]-'a'+1)*p[j]; FOR(j,1,L) { f[i][j]=f[i+1][j]; if (g[len[j]]==c[j]) f[i][j]=i+len[j]-1; } } int true_l; if (a[n]!='*') true_l=L-1;else true_l=L; int ans=0; FOR(i,1,m) { int flag=1; for (j=n;j&&a[j]!='*';j--) if (a[j]!=b[i+m-1-(n-j)]) {flag=0;break;} if (!flag||j==0&&n!=m) continue; int P=i,k; FOR(k,1,true_l) { if (k==1&&a[1]!='*'&&f[i][k]!=i+len[1]-1) break; P=f[P][k]+1; } if (k>true_l&&P<=i+m-(n-j)) ans++; } printf("%d\n",ans); return 0; } |
|
|
| Total comments: 0 | |