方法没什么说的,就是枚举位置,正反,模拟一下就行了.关键是查找,离散化的问题
开始以为是个stl的题目,用map一做.tle...就用自己的hash,RE
今天看到了一篇文章讲的是常用字符串hash函数,试着做了一下,A了..
由此说明好的 hash函数很重要...
/*ELF hash + 链表处理冲突 141ms*/
#include <cstdio>
#include <cstring>
#include <memory.h>
#define MC 9461
using namespace std;
struct node
{
char str[100];
node *next;
} *all[10000];
void hash(char *str1,char *str2);
int ans=0;
int main(void)
{
int t,i,j;
char s[100],r1[100],r2[100],t1[100],t2[100];
scanf("%d",&t);
while (t--)
{
memset(all,0,sizeof(all));
ans=0;
scanf("%s",s);
int len=strlen(s);
for ( i=0; s[i]; i++)
{
for ( j=0; j<i; j++)
r1[j]=s[j];
r1[j]='\0';
for ( j=i; s[j]; j++)
t1[j-i]=s[j];
t1[j-i]='\0';
for ( j=i-1; j>=0; j--)
r2[i-1-j]=s[j];
r2[i-1-j]='\0';
for ( j=len-1; j>=i; j--)
t2[len-1-j]=s[j];
t2[len-1-j]='\0';
hash(r1,t1),hash(t1,r1),hash(r1,t2),hash(t2,r1);
hash(r2,t1),hash(t1,r2),hash(r2,t2),hash(t2,r2);
}
printf("%d\n",ans);
}
return 0;
}
void hash(char *str1,char *str2)
{
char str[100],*strm;
strcpy(str,str1);
strcat(str,str2);
unsigned int hash = 0;
unsigned int x = 0;
strm=str;
while (*strm)
{
hash = (hash << 4) + *strm;
strm++;
if ((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
hash &= ~x;
}
}
int t=(hash & 0x7FFFFFFF)%MC;
node *p,*q;
for ( p=q=all[t]; p&&strcmp(str,p->str); q=p,p=p->next);
if (p) return;
ans++;
if (p==all[t])
{
all[t]=new node;
p=all[t];
}
else q->next=new node,p=q->next;
p->next=NULL;
strcpy(p->str,str);
}