转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1307515870
大致题意：
给定一个字符串，从任意位置把它切为两半，得到两条子串
定义 子串1为s1，子串2为s2，子串1的反串为s3，子串2的反串为s4
现在从s1 s2 s3 s4中任意取出两个串组合，问有多少种不同的组合方法
规定：
（1） 串Si不能和其 反串 组合
（2） Si+Sj 与 Sj+Si 是两种组合方式（但未必是不同的组合方式）
解题思路：
利用hash表查重
穷举全部组合的情况，每枚举一个就记录一次，假如后面枚举的组合已经存在记录，说明组合重复，计数器不变，否则计数器+1
本题不能用STL的map映射，map太慢会超时
自己写Hash表吧！
可以认为i为权重，利用字母的ASCII得到key
解决冲突方法为链地址法
1 //Memory Time
2 //2380K 157MS
3
4 #include<iostream>
5 using namespace std;
6
7 const int size=80;
8 const int mod=99991;
9 int count; //计数器
10
11 typedef struct HASH
12 {
13 char s[size];
14 struct HASH* next;
15 HASH()
16 {
17 next=0; //0<=>NULL
18 }
19 }Hashtable;
20
21 Hashtable* Hash[mod]; //hash[]是指针数组，存放地址
22
23 void hash(char* s);
24 void StrCopy(char* s1,char* s2); //把s2复制到s1，要确保s1.len>s2.len
25 void StrCut(char* s,char* s1,char* s2,int k,int slen); //把s前k个字符(0~k-1)复制到s1，第k到slen的字符复制到s2
26 void StrInvert(char* s1,char* s2,int len); //把s1逆序存放到s2
27 char* StrCat(char* s1,char* s2,char* str); //把s2连接到s1后，存放到s
28
29 int main(void)
30 {
31 int n;
32 cin>>n;
33 while(n--)
34 {
35 char train[size];
36 cin>>train;
37 int len=strlen(train);
38 if(len==1)
39 {
40 cout<<1<<endl;
41 continue;
42 }
43
44 memset(Hash,0,sizeof(Hash)); //0 <-> NULL
45 count=0;
46
47 for(int i=1;i<=len-1;i++) //i为火车分开的两部分中，前一部分的节数
48 {
49 char s1[size],s2[size];
50 char s3[size],s4[size]; //s3为s1的逆序，s4为s2的逆序
51 char str[size];
52
53 StrCut(train,s1,s2,i,len);
54 StrInvert(s1,s3,i);
55 StrInvert(s2,s4,len-i);
56
57 /*标记组合方式*/
58
59 hash(train); //s1与s2组合就是原来的train
60 StrCat(s2,s1,str);
61 hash(str);
62 StrCat(s1,s4,str);
63 hash(str);
64 StrCat(s4,s1,str);
65 hash(str);
66 StrCat(s3,s2,str);
67 hash(str);
68 StrCat(s2,s3,str);
69 hash(str);
70 StrCat(s3,s4,str);
71 hash(str);
72 StrCat(s4,s3,str);
73 hash(str);
74 }
75
76 cout<<count<<endl;
77 }
78 return 0;
79 }
80
81
82 void hash(char* s)
83 {
84 char* ps=s;
85
86 int key=0;
87 for(int i=1;*ps;i++)
88 key+=*(ps++)*i;
89 key%=mod;
90
91 if(!Hash[key]) //新key
92 {
93 Hashtable* pn=new Hashtable; //由于要存放数据，必须申请空间
94 //Hashtable* pn;只是单纯申请一个地址空间
95 StrCopy(pn->s,s);
96 Hash[key]=pn;
97
98 count++;
99 }
100 else //key值冲突
101 {
102 Hashtable* pn=Hash[key]; //pn指向冲突位置的链表开头
103
104 if(!strcmp(pn->s,s))
105 return; //不计数返回
106 else
107 {
108 while(pn->next)
109 {
110 if(!strcmp(pn->next->s,s)) //地址冲突且字符串相同
111 return;
112
113 pn=pn->next;
114 }
115
116 //地址冲突但字符串不同
117
118 Hashtable* temp=new Hashtable;
119 StrCopy(temp->s,s);
120 pn->next=temp; //记录新字符串
121
122 count++;
123 }
124 }
125 return;
126 }
127
128 void StrCopy(char* s1,char* s2) //把s2复制到s1
129 {
130 char* ps1=s1;
131 char* ps2=s2;
132 while(*ps2)
133 *(ps1++)=*(ps2++);
134 *ps1='\0';
135
136 return;
137 }
138
139 void StrCut(char* s,char* s1,char* s2,int k,int slen) //把s前k个字符(0~k-1)复制到s1，第k到slen的字符复制到s2
140 {
141 int i,ps1=0,ps2=0;
142
143 for(i=0;i<k;i++)
144 s1[ps1++]=s[i];
145 s1[ps1]='\0';
146
147 for(;i<slen;i++)
148 s2[ps2++]=s[i];
149 s2[ps2]='\0';
150
151 return;
152 }
153
154 void StrInvert(char* s1,char* s2,int len) //把s1逆序存放到s2
155 {
156 int ps=0;
157 s2[len]='\0';
158 for(int i=len-1;i>=0;i--)
159 s2[i]=s1[ps++];
160
161 return;
162 }
163
164 char* StrCat(char* s1,char* s2,char* str) //把s2连接到s1后，存放到s
165 {
166 int i,ps=0;
167 for(i=0;s1[i]!='\0';i++)
168 str[ps++]=s1[i];
169 for(i=0;s2[i]!='\0';i++)
170 str[ps++]=s2[i];
171 str[ps]='\0';
172
173 return str;
174 }