http://poj.org/problem?id=3007
第一次用STL做的，TLE了，自己构造字符串哈希函数才可以。。
TLE代码：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int cnt = ,j;
char ss[];
string str,s,s1,s2;
map<string,int>v;
cin>>str;
s = str;
int len = str.size(); for (int i = ; i < len; i++)
{
s = str;
string::iterator it = s.begin();
for (j = ; j < i; j++)
ss[j] = str[j];
ss[j] = '\0';
s1 = ss;
s.erase(it,it+i);
s2 = s;
for (int k = ; k <= ; k++)
{
if (v[s1+s2]==)
{
v[s1+s2]++;
cnt++;
}
if (v[s2+s1]==)
{
v[s2+s1]++;
cnt++;
}
if (k==)
reverse(s1.begin(),s1.end());
else if (k==)
reverse(s2.begin(),s2.end());
else if (k==)
reverse(s1.begin(),s1.end());
}
}
printf("%d\n",cnt);
}
return ;
}
AC代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=;
const int MOD=;
int cnt = ; struct node
{
char s[];
struct node *next;
}*hash[N]; void Hash(char *s1,char *s2)
{
char ss[],*str;
strcpy(ss,s1);
strcat(ss,s2);
str = ss;
unsigned int key = ;
while(*str)
{
key = key*+(*str++);
}
key%=;
if (!hash[key])
{
hash[key] = new node;
strcpy(hash[key]->s,ss);
hash[key]->next = NULL;
cnt++;
}
else
{
struct node *p = hash[key];
if(strcmp(p->s,ss)==)
return ;
while(p->next)
{
if (!strcmp(p->next->s,ss))
return ;
p = p->next;
}
p->next = new node;
strcpy(p->next->s,ss);
p->next->next = NULL;
cnt++;
}
}
int main()
{ char s[],s1[],s2[],s3[],s4[];
int n,j;
scanf("%d",&n);
while(n--)
{
cnt = ;
scanf("%s",s);
int len = strlen(s);
memset(hash,,sizeof(hash));
for (int i = ; i < len; i++)
{
for (j = ; j < i; j++)
s1[j] = s[j];
s1[j] = '\0';
for (j = i; j < len; j++)
s2[j-i] = s[j];
s2[j-i] = '\0';
strcpy(s3,s1);
strcpy(s4,s2);
reverse(s1,s1+i);
reverse(s2,s2+len-i);
Hash(s3,s4);
Hash(s4,s3);
Hash(s1,s4);
Hash(s4,s1);
Hash(s2,s3);
Hash(s3,s2);
Hash(s1,s2);
Hash(s2,s1); }
printf("%d\n",cnt);
}
return ;
}
有关字符串哈希函数的经典算法
unsigned int SDBMHash(char *str)
{
unsigned int hash = ; while (*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << ) + (hash << ) - hash;
} return (hash & 0x7FFFFFFF);
} // RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b = ;
unsigned int a = ;
unsigned int hash = ; while (*str)
{
hash = hash * a + (*str++);
a *= b;
} return (hash & 0x7FFFFFFF);
} // JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = ; while (*str)
{
hash ^= ((hash << ) + (*str++) + (hash >> ));
} return (hash & 0x7FFFFFFF);
} // P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * );
unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * ) / );
unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / );
unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
unsigned int hash = ;
unsigned int test = ; while (*str)
{
hash = (hash << OneEighth) + (*str++);
if ((test = hash & HighBits) != )
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
} return (hash & 0x7FFFFFFF);
} // ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = ;
unsigned int x = ; while (*str)
{
hash = (hash << ) + (*str++);
if ((x = hash & 0xF0000000L) != )
{
hash ^= (x >> );
hash &= ~x;
}
} return (hash & 0x7FFFFFFF);
} // BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = ; // 31 131 1313 13131 131313 etc..
unsigned int hash = ; while (*str)
{
hash = hash * seed + (*str++);
} return (hash & 0x7FFFFFFF);
} // DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = ; while (*str)
{
hash += (hash << ) + (*str++);
} return (hash & 0x7FFFFFFF);
} // AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash = ;
int i; for (i=; *str; i++)
{
if ((i & ) == )
{
hash ^= ((hash << ) ^ (*str++) ^ (hash >> ));
}
else
{
hash ^= (~((hash << ) ^ (*str++) ^ (hash >> )));
}
} return (hash & 0x7FFFFFFF);
}