|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <sstream> #define SZ 10000017 using namespace std; char b[30]; char str[3000000][25];//3000000 int parent[10000017]; int strmap[3000000]; int gethash(char s[]) { int seed=31; int v=0; for(int i=0;i<strlen(s);i++) { v= v*seed+(s[i]-'0'); } return (v&0x7FFFFFFF)%SZ; } bool insert(int position) { int _hash = gethash(str[position]); int next=parent[_hash]; while(next!=-1) { if(!strcmp(str[position],str[next])) break; next=strmap[next]; } if(next==-1) { strmap[position]=parent[_hash]; parent[_hash]=position; return 1; } return 0; } int main() { string s; stringstream ss; int t,kase=1; int cnt; int n,m,i; gets(b); sscanf(b,"%d",&t); //cin>>t; //getchar(); while(t--) { //getline(cin,s); gets(b); sscanf(b,"%d%d",&m,&n); //ss.clear(); //ss<<s; //ss>>m>>n; cnt=0; memset(parent,-1,sizeof(parent)); //memset(strmap,0,sizeof(strmap)); for(i=0;i<m;i++) //getline(cin,str[i]); gets(str[i]); for(int j=0;j<n;j++) { //getline(cin,str[i]); gets(str[i]); for(int k=0;k<m;k++) { //str[i+k+1]=str[k]; strcpy(str[i+k+1],str[k]); //str[i+k+1].append(str[i]); strcat(str[i+k+1],str[i]); if(insert(i+k+1)) cnt++; //x++; } i=i+m+1; } cout<<"Case "<<kase++<<": "<<cnt<<"\n"; } return 0; } |