【POJ2752】Seek the Name, Seek the Fame(hash)
题目地址:http://poj.org/problem?id=2752题目:每组数据给定一个字符串,从小到大输出既是前缀又是后缀的子串的长度ac代码:直接用hash做,比kmp简单很多#include <cmath>#include <iostream>#include <cstdio>#include <string&g...
·
题目地址:http://poj.org/problem?id=2752
题目:
每组数据给定一个字符串,从小到大输出既是前缀又是后缀的子串的长度
ac代码:
直接用hash做,比kmp简单很多
#include <cmath>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef unsigned long long ll;
const ll maxn = 400005;
ll p = 233333,len = 0;
char s[maxn];
ll has[maxn], power[maxn];
void init()//预处理p^n
{
power[0] = 1;
for(int i = 1; i < maxn; i++)
power[i] = power[i - 1] * p;
}
int main ()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
init();
while(~scanf("%s",s+1))
{
len = strlen(s + 1);
has[0] = 0;
for(int i = 1; i <= len; i++)
has[i] = has[i - 1] * p + (ll)(s[i] - 'a' + 1);
for(int i = 1; i <= len ; i++)
{
ll tmp = has[len] - has[len - i] * power[i];
if(tmp == has[i])
printf("%d ", i);
}
printf("\n");
}
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)