http://poj.org/problem?id=3007
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 600000
using namespace std; struct node
{
char s[];
node *next;
};
int ans;
node *hash[maxn]; void insert(char s[])
{
int k=strlen(s);
int sum=;
for(int i=; i<k; i++)
{
sum+=s[i]*i;
}
//printf("%d %s\n",sum,s);
if(!hash[sum])
{
node *p=new node();
strcpy(p->s,s);
hash[sum]=p;
ans++;
//printf("*%d %s\n",sum,s);
}
else
{
node *p=hash[sum];
if(!strcmp(p->s,s)) return ;
else
{
while(p->next!=NULL)
{
if(!strcmp(p->next->s,s))
return ;
p=p->next;
}
node *q=new node();
strcpy(q->s,s);
p->next=q;
ans++;
//printf("*%d %s\n",sum,s);
}
}
return ;
} void change(char s1[],char s2[],char s3[],char s4[])
{
int k1=strlen(s1);
int k2=strlen(s2);
int t1=,t2=;
for(int i=k1-; i>=; i--)
{
s3[t1++]=s1[i];
}
s3[t1]='\0';
for(int j=k2-; j>=; j--)
{
s4[t2++]=s2[j];
}
s4[t2]='\0';
} void merge(char str1[],char str2[],char str3[])
{
int m=;
int k1=strlen(str1);
int k2=strlen(str2);
for(int i=; i<k1; i++)
{
str3[m++]=str1[i];
}
for(int j=; j<k2; j++)
{
str3[m++]=str2[j];
}
str3[m]='\0';
} int main()
{
int t;
char str[],s1[],s2[],s3[],s4[],s[];
scanf("%d",&t);
while(t--){
ans=;
scanf("%s",str);
if(strlen(str)==){
printf("1\n");
continue;
}
memset(hash,,sizeof(hash));
int k=strlen(str);
for(int i=; i<=k-; i++)
{
//printf("%d\n",i);
int t1=,t2=,j;
for(j=; j<i; j++)
{
s1[t1++]=str[j];
}
s1[t1]='\0';
for(; j<k; j++)
{
s2[t2++]=str[j];
}
s2[t2]='\0';
change(s1,s2,s3,s4);
merge(s1,s4,s);
insert(s);
merge(s1,s2,s);
insert(s);
merge(s2,s3,s);
insert(s);
merge(s4,s1,s);
insert(s);
merge(s2,s1,s);
insert(s);
merge(s3,s2,s);
insert(s);
merge(s4,s3,s);
insert(s);
merge(s3,s4,s);
insert(s);
}
printf("%d\n",ans);
}
return ;
}