| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:哪位高手帮忙看一下啊,都wa到无语了……In Reply To:哪位高手帮忙看一下啊,都wa到无语了…… Posted by:sun3673181 at 2008-10-08 12:57:07 > #include<cstdio>
> #include<iostream>
> using namespace std;
>
> //把每行计算成一整数,用kmp算法让每个星座进行行比较
>
> char data[1000][1001],cons[100][50][51];
> long long num,data2[1000],cons2[100][50];
> int N,M,T,P,Q;
> int kmp[100][50];
> bool used[100];
>
> int compute(){
> int ccount=0,i,j,k,l;
> for(l=0;l<T;l++){
> for(k=j=0;k<N&&j<P;k++)
> if(data2[k]==cons2[l][j])
> j++;
> else if(j)
> j=kmp[l][j-1]+1,k--;
> if(j==P) used[l]=true;
> }
>
> for(i=0;i<M-Q;i++){
> for(j=0;j<N;j++)
> {
> data2[j]<<=1;
> data2[j]&=num;
> if(data[j][i+Q]=='*')
> data2[j]++;
> }
>
> for(l=0;l<T;l++){
> if(used[l])
> continue;
> for(k=j=0;k<N&&j<P;k++)
> if(data2[k]==cons2[l][j])
> j++;
> else if(j)
> j=kmp[l][j-1]+1,k--;
> if(j==P) used[l]=true;
> }
> }
> for(i=0;i<T;i++)
> if(used[i]) ccount++;
> return ccount;
> }
>
> int main(){
> int ccount=1;
> while(scanf("%d%d%d%d%d",&N,&M,&T,&P,&Q)&&(N|M|T|P|Q)){
> int i,j,k;
> for(i=0;i<N;i++)
> for(scanf("%s",&data[i]),data2[i]=0,j=0;j<Q;j++)
> {
> data2[i]<<=1;
> if(data[i][j]=='*')
> data2[i]++;
> }
> for(i=0;i<T;i++){
> for(j=0;j<P;j++)
> for(scanf("%s",&cons[i][j]),cons2[i][j]=0,k=0;k<Q;k++)
> {
> cons2[i][j]<<=1;
> if(cons[i][j][k]=='*')
> cons2[i][j]++;
> }
> for(kmp[i][0]=-1,j=1;j<P;kmp[i][j++]=0);
> for(j=1;j<P;j++){
> for(k=kmp[i][j-1];k>=0&&!(cons2[i][k+1]==cons2[i][j]);k=kmp[i][k]);
> kmp[i][j]=(cons2[i][k+1]==cons2[i][j]?k+1:-1);
> }
> }
> if(P>N||Q>M){
> printf("Case %d: %d\n",ccount++,0);
> continue;
> }
> (num=(1<<Q))--;
> memset(used,0,sizeof(used));
> printf("Case %d: %d\n",ccount++,compute());
> }
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator