poj 3007 Organize Your Train part II (哈希)

题目：http://poj.org/problem?id=3007
题目不难，，，如果用STL的话会很简单，但会TLE
后来我敲了一个tri树。。爆内存。。
又改成哈希以后结果。。。还是TLE。。。
后来看的别人的报告，，，结果是他们用的是指针数组，我的不是。。。还是指针快啊。。
代码：
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5  char str[10][81];
  6  int num;
  7  int len;
  8  const int mod=99991;
  9 typedef struct node
 10 {
 11     char st[81];
 12     struct node *next;
 13     node()
 14     {
 15         next=NULL;
 16     }
 17 }has;
 18 has *hash[mod+1];
 19 void hhash()
 20 {
 21     int i,j;
 22 
 23     for(i=0;i<8;i++)
 24     {
 25         int key=0;
 26         for(j=0;j<len;j++)
 27         {
 28             key+=str[i][j]*(j+1)%mod;
 29         }
 30         key%=mod;
 31         //cout<<"key="<<key<<endl;
 32         if(!hash[key])
 33         {
 34             has *p=new has;
 35             strcpy(p->st,str[i]);
 36             hash[key]=p;
 37             num++;
 38         }
 39         else
 40         {
 41             int flag=0;
 42             has *p=hash[key];
 43             if(!strcmp(p->st,str[i]))
 44             continue;
 45             else
 46             {
 47                 while(p->next)
 48                 {
 49                     if(!strcmp(p->next->st,str[i]))
 50                     {
 51                         flag=1;
 52                         break;
 53                     }
 54                     p=p->next;
 55                 }
 56                 if(flag==0)
 57                 {
 58                     has *q=new has;
 59                     strcpy(q->st,str[i]);
 60                     p->next=q;
 61                     num++;
 62                 }
 63             }
 64         }
 65     }
 66 }
 67 
 68 int main()
 69 {
 70     int m;
 71     scanf("%d",&m);
 72     getchar();
 73     while(m--)
 74     {
 75 
 76         gets(str[0]);
 77         len=strlen(str[0]);
 78         int i,j;
 79         int k[10];
 80         num=0;
 81          //int bb;
 82         //cout<<"len="<<len<<endl;
 83         //for(i=0;i<mod;i++)
 84         //hash[i].next=NULL;
 85         memset(hash,0,sizeof(hash));
 86         for(i=0;i<len-1;i++)
 87         {
 88             memset(k,0,sizeof(k));
 89             for(j=0;j<=i;j++)
 90             {
 91                 str[1][k[1]]=str[0][j];
 92                 k[1]++;
 93             }
 94             for(j=i;j>=0;j--)
 95             {
 96                 str[2][k[2]]=str[0][j];
 97                 k[2]++;
 98                 str[3][k[3]]=str[0][j];
 99                 k[3]++;
100             }
101             for(j=i+1;j<len;j++)
102             {
103                 str[2][k[2]]=str[0][j];
104                 k[2]++;
105                 str[4][k[4]]=str[0][j];
106                 k[4]++;
107                 str[5][k[5]]=str[0][j];
108                 k[5]++;
109             }
110             for(j=len-1;j>i;j--)
111             {
112                 str[1][k[1]]=str[0][j];
113                 k[1]++;
114                 str[3][k[3]]=str[0][j];
115                 k[3]++;
116                 str[6][k[6]]=str[0][j];
117                 k[6]++;
118                 str[7][k[7]]=str[0][j];
119                 k[7]++;
120             }
121             for(j=0;j<=i;j++)
122             {
123                 str[4][k[4]]=str[0][j];
124                 k[4]++;
125                 str[6][k[6]]=str[0][j];
126                 k[6]++;
127             }
128             for(j=i;j>=0;j--)
129             {
130                 str[5][k[5]]=str[0][j];
131                 k[5]++;
132                 str[7][k[7]]=str[0][j];
133                 k[7]++;
134             }
135             for(j=1;j<8;j++)
136             str[j][len]='\0';
137             /*cout<<"i="<<i<<endl;
138             for(bb=0;bb<8;bb++)
139             {
140                 cout<<"bb="<<bb<<" ";
141                puts(str[bb]);
142             }*/
143             hhash();
144         }
145         cout<<num<<endl;
146     }
147     return 0;
148 }