UOJ #5.[NOI2014]动物园 | Kyons'Blog 




 
 
 
 



 
 



UOJ #5.[NOI2014]动物园

序言

  这个题写的我好迷啊==

题目简述

  园长想让你求一个字符串的”不互相重叠的公共前后缀个数”然后再乘起来.一大骡子的字,总结一下就是这个意思.

解析

  如果你不会$KMP$….那我也没办法(笑)
  我们知道,$next$保存的是有重叠部分的最大长度.那么我们在它计算的过程中,把当前$next[i]$的位置,存一个长度$cnt[i]$,啥意思?
  我$next[i]$从头扫到尾,相当于一个递推得到最大长度.同时进行$cnt[i]$从头扫到尾,相当于递推得到最大个数.
  然后再用$next[]$数组,找到不重复的位置,也就是$j\leq{i/2}$这样的位置,计算$cnt$,完成.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

typedef long long ll;

const int INF = 1e9;
const int MAXN = 2e6 + 10;

int n[MAXN],len,f[MAXN];
char t[MAXN];
void getnext(char *t)
{
n[0] = 0,n[1]=1;
f[0] = -1, f[1] = 0;
for (int i = 1, j = 0; i < len; i++) {
while (j != -1 && t[i] != t[j])
j = f[j];
++j;
f[i + 1] = j;
n[i+1] = n[j]+1;
}
}
const int mod = 1e9 + 7;
int main() {
int k;
cin >> k;
while (k--) {
cin >> t;
len = strlen(t);
getnext(t);
ll ans = 1;
for (int i = 1,j=0; i < len; i++) {
while (j != -1 && t[i] != t[j])
j = f[j];
j++;
while (j * 2 > i + 1)
j = f[j];
ans = ans * (ll)(n[j] + 1)%mod;
}
cout << ans << endl;
}
return 0;
}

 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载