OKR-Periods of Words
题目描述
输入格式
输出格式
样例
样例输入
8
babababa
样例输出
24
1. 题目到底要让我们求什么：
- （首先这是一道kmp的题）这是每个位置kmp的数值，代表它的border（真前缀和后缀）
- 这是由题意得出的每个位置的最长周期（
还没什么头绪）
-
结合这张图来看：黑色字为每个位置的编号（用i表示）
我是从1开始存图的，绿色字为每个位置的最小的既是前缀又是后缀（非真前缀）（用j表示）
这样用i-j恰好等于蓝字（题目要求的最大周期Q） o(￣▽￣)ブ -
既然这样我们就只需求出没个位置的最小的既是前缀又是后缀-->j，再用该位置编号去减它就可以了
2. 怎么求最小的既是前缀又是后缀-->j：
-
这就需要用到kmp了，每次往前递归，当该值的border=0时，返回，此时这个值就是就是我们想要的j
但这里有一个限制条件：我们的最大周期应该>=(i/2) -
当某个位置的kmp值为0时，如下图：j的初值设置就为i，此时不会进入while循环和第一个if语句，i的j值就为i
（结合样例中的1，2位置理解）
for (int i=2;i<=len;i++) //查找每个i的最长周期 {int j=i;while (p[j]) j=p[j]; //记忆化优化 if (p[i]) p[i]=j;//p[i]为i能跳的最小值//i-j表示i的最长周期//判断合法性：只有当该周期>=i长度的一半时合法//（即题目中QQ能覆盖完A的全部） if ((i-j)>=(i>>1))ans+=i-j; }
3.记忆化优化：
- 这个方法如果不用优化的话会T，当然优化方法不止记忆化，但本蒟蒻只会记忆化
if (p[i]) p[i]=j;//p[i]为i能跳的最小值
- 当p[i]不为0时，更新p[i],下次就能一次性跳到啦！
4.代码
此处为代码：（p[maxn]数组存储的是跑kmp的值）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+10;
char a[maxn];
int p[maxn],len;
ll ans;
void kmp()
{for (int i=2,j=0;i<=len;i++) {while (j&&a[i]!=a[j+1]) j=p[j];if (a[j+1]==a[i]) j++;p[i]=j;}
}
void solve()
{//i=1时没有周期 for (int i=2;i<=len;i++) //查找每个i的最长周期 {int j=i;while (p[j]) j=p[j]; //记忆化优化 if (p[i]) p[i]=j;//p[i]为i能跳的最小值//i-j表示i的最长周期//判断合法性：只有当该周期>=i长度的一半时合法//（即题目中QQ能覆盖完A的全部） if ((i-j)>=(i>>1))ans+=i-j; }printf("%lld",ans);
}
int main()
{scanf("%d",&len);scanf("%s",a+1);kmp();solve();return 0;
}
完结撒花！
