poj 3087 模拟（ELFHash模版，字符串哈希）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 102
 9 
10 int N,C;
11 char s1[MAXN],s2[MAXN],s12[MAXN<<1],ans[MAXN<<1];
12 
13 //*****************ELFhash***********
14 #define HASH 9901
15 char table[9901][MAXN];
16 int len;
17 int ELFHash(char a[MAXN])        
18 {
19     int h = 0;
20     int x  = 0;
21     for(int i=0;i<len;++i)
22     {
23         h = (h << 4) + (a[i]);
24         if ((x = h & 0xF0000000L) != 0)
25         {
26             h ^= (x >> 24);
27             h &= ~x;
28         }
29     }
30     return h % HASH;
31 }
32 bool is_in(char a[])    //ELFHash函数对字符串判重,没有的时候插入
33 {
34     int i=ELFHash(a);
35     while(strlen(table[i])>0&&strcmp(a,table[i])!=0)
36         i=(i+1)%HASH;
37     if(strlen(table[i])==0)
38     {
39         strcpy(table[i],a);
40         return false;
41     }
42     return true;
43 }
44 //***********************************
45 
46 int main()
47 {
48     scanf("%d",&N);
49     for(int cas=1;cas<=N;cas++)
50     {
51         scanf("%d",&C);getchar();
52         len=C*2;
53         memset(s1,0,sizeof(s1));
54         memset(s2,0,sizeof(s2));
55         memset(s12,0,sizeof(s12));
56         memset(ans,0,sizeof(ans));
57         memset(table,0,sizeof(table));
58         gets(s1);
59         gets(s2);
60         gets(ans);
61         printf("%d ",cas);
62         int step=0;
63         while(1)
64         {
65             step++;
66             for(int i=0;i<len;i+=2)
67                 s12[i]=s2[i/2];
68             for(int i=1;i<len;i+=2)
69                 s12[i]=s1[i/2];
70             s12[len]='\0';
71             //cout<<s1<<endl;
72             //cout<<s2<<endl;
73             if(strcmp(ans,s12)==0)
74             {
75                 printf("%d\n",step);
76                 break;
77             }
78             else if(is_in(s12))
79             {
80                 printf("-1\n");
81                 break;
82             }
83             for(int i=0;i<C;i++)
84                 s1[i]=s12[i];
85             for(int i=0;i<C;i++)
86                 s2[i]=s12[i+C];
87         }
88     }
89     return 0;
90 }