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);
}

最新文章

  1. js 批量设置css样式
  2. 向架构师进军--&gt;可重用架构资源
  3. jQuery-强大的jQuery选择器 (详解)[转]
  4. ESXi 6.0 配置
  5. LINUX下如何开启FTP服务器
  6. Nginx服务测试时的一些配置:wireshark、常用搜索URL格式、关闭防火墙、siege
  7. Spring MVC开发环境的搭建和实例
  8. java的RMI(Remote Method Invocation)
  9. operator new3种情况详解
  10. JS焦点图,JS 多个页面放多个焦点图
  11. poj2761Feed the dogs(划分树-区间K值)
  12. compute post expression
  13. WebGIS中通过行列号来换算出多种瓦片的URL 之离线地图(转载)
  14. IdentityServer Topics(3)- 定义客户端
  15. 机器学习——XGBoost大杀器,XGBoost模型原理,XGBoost参数含义
  16. FFT Cheetsheet
  17. 微信小程序之微信登陆 —— 微信小程序教程系列(20)
  18. LY.JAVA面向对象编程.工具类中使用静态、说明书的制作过程、API文档的使用过程
  19. Django中的视图
  20. FromBottomToTop团队项目总结

热门文章

  1. javascript常用功能函数
  2. 【sqli-labs】 less45 POST -Error based -String -Stacked Blind(POST型基于盲注的堆叠字符型注入)
  3. jinkins配置python虚拟环境
  4. 原生Ajax的使用——含开放API接口
  5. 基本数据类型:字符串(str)
  6. 02. 爬取get请求的页面数据
  7. LINUX 查看硬件配置命令
  8. nyoj_19_擅长排列的小明_201403011600
  9. kendo Grid的toolbar自定义
  10. [bzoj2850]巧克力王国_KD-Tree