1511: [POI2006]OKR-Periods of Words

https://www.lydsy.com/JudgeOnline/problem.php?id=1511

题意：

　　对于一个串的所有前缀，设为s，求出它的最大前缀Q，使得s为QQ的前缀。求最大前缀长度的和。

分析：

　　KMP+next数组。

　　next数组表示的是这个字符串的最大的公共前缀后缀。对于字符串s，设其next为j，那么它的前j个和后j个是相等的。如果这j个没有重叠，那么所求的最长前缀就是1~n-j。把这个前缀重复两遍可以包含s。所求的就是最小的这样border，最小的j（j越小，相当于n个字符，后j个更少，那么剩余的所求的前缀就越长了）。然后求出最小的公共前后缀。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 char A[N];

 int p[N];

 int main() {

     int n; cin >> n;

     scanf("%s",A+);

     p[] = ;

     for (int i=; i<=n; ++i) {

         int j = p[i-];

         while (j && A[i]!=A[j+]) j = p[j];

         if (A[i] == A[j+]) j++;

         p[i] = j;

     }

     LL ans = ;

     for (int i=; i<=n; ++i) {

         int j = i;

         while (p[j]) j = p[j]; // 这里看到这样写的p[p[j]]，其实每个p[i]在下面已经更新了，不需要跳很多次。

         if (p[i] != ) p[i] = j; // 类似于记忆化，前缀i的跳的最优位置。

         ans += i - j;

     }

     cout << ans;

     return ;

 }

巴特西

1511: [POI2006]OKR-Periods of Words

1511: [POI2006]OKR-Periods of Words

最新文章

热门文章