POJ2406 power strings—

POJ2406 power strings——哈希/KMP

本文主要是介绍POJ2406 power strings——哈希/KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门
题目大意：
给定若干个长度 ≤ $10^6$ 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如： $ababab$ 则最多有 $3$ 个 $ab$ 连接而成。

样例输入：
abcd
aaaa
ababab
. //当读入为.时结束程序
样例输出
1
4
3

这道题是一道有趣的题，有两种思路，第一种是哈希。
我们考虑哈希的过程，就以 $ababab$ 为例，则整个串的哈希值为（我的乘数是233）
$233*(233*(233*(233*(233*a+b)+a)+b)+a)+b$
这是最基础的哈希过程，我们把它拆开，就成了下式：
$(a*233^5+b*233^4)+(a*233^3+b*233^2)+(a*233+b)$
我们考虑 $ab$ 的哈希值，为 $a*233+b$ ，设 $ab$ 的哈希值为 $x$ ，则整个串的哈希值为 $x*233^4+x*233^2+x*233^0$
其实就是 $x$ 乘以一个等比数列，而这个数列为 $1,233^{l},233^{2l}……233^{L-l}$ 其中 $l$ 为我们要求的字串的长度， $L$ 为大串的长度，根据等比数列公式，这个数列的和是 $\frac{1-p^L}{1-p^l}$ ,所以枚举 $l$ ，并求出当前串的哈希值，如果其乘以左边的数等于大串的哈希值，那么我们要找的就是这个字串。（由于 $p^l$ 会很大，所以这道题要使用乘法逆元）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MD 1000000007
#define ll long long
using namespace std;
char s[1000005];
ll l,a,b,lst,bin[1000005];
ll pows(ll a,ll b){ll base=1;while(b){if(b&1) base=base*a%MD;a=a*a%MD;b/=2;}return base;
}
int main()
{bin[0]=1;for(ll i=1;i<=1000000;i++) bin[i]=bin[i-1]*233%MD;while(~scanf("%s",s+1)){if(s[1]=='.') break;l=strlen(s+1);lst=0;a=0;b=0;for(ll i=1;i<=l;i++) a=(a*233+s[i])%MD;for(ll i=l;i>=1;i--){if(l%i) continue;for(ll j=lst+1;j<=l/i;j++) b=(b*233+s[j])%MD;lst=(l/i);ll x=b;x=x*(bin[l]-1+MD)%MD;x=x*pows(bin[l/i]-1,MD-2)%MD;if(x==a){printf("%d\n",i);break;}}}return 0;
}

第二种方法十分巧妙，运用的是KMP算法。首先我们求出这个字符串的 $next$ 。我们考虑 $next$ 的性质，如果一个长为 $L$ 字符串被一个小字符串分成 $m$ 条，那么它的 $next$ 是多少？ $L*\frac{m-1}{m}$ ,我们因为 $next$ 是它最长的不等于自己的相同的前缀和后缀。因为不等于自己，又要最长，所以只能乘以 $\frac{m-1}{m}$ ，所以如果真的能被分成 $m$ 条，那么 $L-nxt[L]$ 整除 $L$ ，并且答案就是 $\frac{L}{L-nxt[L]}$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000005];
int nxt[1000005],l;
void getnext(){int k=-1,j=0;nxt[0]=-1;while(j<l){if(k==-1||s[k]==s[j]){k++;j++;nxt[j]=k;}else k=nxt[k];}
}
int main()
{while(~scanf("%s",s)){if(s[0]=='.') break;l=strlen(s);getnext();printf("%d\n",l%(l-nxt[l])?1:l/(l-nxt[l]));}return 0;
}