[POI2012]OKR-A Horrible Poem hash

题面:洛谷

题解:

  首先我们需要知道一个性质,串s的最小循环节 = len - next[len].其中next[len]表示串s的一个最长长度使得s[1] ~ s[next[len]] == s[len - next[len] + 1] ~ s[len](详细定义参见KMP)

  至于为什么是成立的可以画图推一下,这个应该是比较常见的性质。

  [POI2012]OKR-A Horrible Poem      hash

  可能画的有点丑。。。

  图中每个绿色方块所代表的串都是相同的,因为第一个绿块显然与下面那块相同,而根据next的定义,它也与第二行第二个绿块相同……以此类推,可以一直递推下去,直到推完整个数组。

  

  对于一个长度为len的串s而言,设它的最小循环节长度为l.

  若$len = p_{1}^{k_{1}} \cdot p_{2}^{k_{2}} \cdot p_{3}^{k_{3}}...p_{t}^{k_{t}}$

  则$len = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdot p_{3}^{a_{3}}...p_{t}^{a_{t}}$其中$a_{i} \le k_{i}$.

  首先一个串的最大循环节长度肯定= len;

  而这个循环节之所以可以变小,是因为这个最大循环节是由很多个最短循环节组成。我们假设最短循环节为X,这这个串可以表示为XXXXXXX(若干个X)

  假设X有b个。那么我们可以每次对b缩减一个b的因子,最后使得b变为1,即使b不断除一个数。

  例如一个串s一开始可以被表示为XXXXXXXX(8个X),即b = 8

  这个时候我们枚举到一个2,于是我们判断原串是否可以被XXXX + XXXX凑出,如果可以,那么b /= 2.

  然后我们判断原串是否可以被XX + XX + XX + XX凑出,如果可以,那么b /= 2.

  依次类推,直到已经没有更小的循环节可以凑出原串位置。

  其中2是b的某个质因子。

  因为b的最大值为len(即循环节为1),所以我们一开始先从len开始,不断枚举len的质因子,看能否消去这个因子,最后剩下的数就是答案。

  判断一个长度是否可以成立,可以用hash判断图中红色部分是否相等

  [POI2012]OKR-A Horrible Poem      hash

  其中绿块长度为x。

  原理就是一开始解释过的KMP求最小循环节。

 #include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 501000
#define p1 1000000007
#define p2 998244353
#define base 26
#define LL long long int n, m, tot, top;
int hash1[AC], hash2[AC], pw1[AC], pw2[AC];
int pri[AC], last[AC], q[AC];
char s[AC];
bool z[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} void get()//欧拉筛
{
for(R i = ; i <= n; i ++)
{
if(!z[i]) pri[++ tot] = i, last[i] = i;
for(R j = ; j <= tot; j ++)
{
int now = pri[j];
if(now * i > n) break;
z[now * i] = true, last[now * i] = now;
if(!(i % now)) break;
}
}
} void pre()
{
n = read();
scanf("%s", s + );
} void build()//求前缀hash值
{
pw1[] = pw2[] = ;
for(R i = ; i <= n; i ++)
{
hash1[i] = (1ll * hash1[i - ] * base + s[i] - 'a' + ) % p1;
hash2[i] = (1ll * hash2[i - ] * base + s[i] - 'a' + ) % p2;
pw1[i] = 1ll * pw1[i - ] * base % p1;//存下base的i次方
pw2[i] = 1ll * pw2[i - ] * base % p2;
}
} LL cal(int l, int r, bool w){
if(!w) return ((1ll * hash1[r] - 1ll * hash1[l - ] * pw1[r - l + ] % p1) + p1) % p1;
else return ((hash2[r] - 1ll * hash2[l - ] * pw2[r - l + ] % p2) + p2) % p2;
} bool check(int l, int r, int x){//测试区间[l, r]的循环结是否可能为x
return (cal(l + x, r, ) == cal(l, r - x, )) && (cal(l + x, r, ) == cal(l, r - x, ));
} void work()
{
m = read();
for(R i = ; i <= m; i ++)
{
int l = read(), r = read(), x = r - l + ;
top = ;
while(x != ) q[++ top] = last[x], x /= last[x];
x = r - l + ;
for(R i = ; i <= top; i ++)
if(check(l, r, x / q[i])) x /= q[i];
printf("%d\n", x);
}
} int main()
{
// freopen("in.in", "r", stdin);
pre();
get();//处理last数组
build();//构建hash数组
work();
// fclose(stdin);
return ;
}

  

上一篇:封装cookie,自定义过期时间,domain,path


下一篇:posix thread 浅谈