洛谷p3435 OKR-Periods of Words

本文主要是介绍洛谷p3435 OKR-Periods of Words，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

反思

我们之前用$kmp$都是用到前缀字串的最长匹配长度，本题则需要利用$pmt$数组找到最短匹配长度

思路

题目中匹配前缀的意思是，在字符串$a$的前缀中，某个前缀自身重复两遍后能把$a$包括进来
如图：

如图，$A$的最长匹配字段显然是$abcabc$
同时容易发现，$A[78]$=$A[12]$，满足$pmt$数组的原则：前后缀相等。且我们要找最长匹配字段，所以要找到最短的匹配的前后缀长度，但$pmt$只能找到最长匹配，要找到最短匹配，我们需要递推$pmt[i],pmt[pmt[i]]...$，直到等于$0$，如上图，$pmt[8]=5,pmt[5]=2,pmt[2]=2$，所以$pmt[5]=2$就是$8$的最短匹配长度

ACcode

#include<bits/stdc++.h>using namespace std;using ll = long long;const int M = 1e6 + 9;
ll pmt[M];void get_pmt(const string& p) {for (int i = 1, j = 0;i < p.size();i++) {while (j && p[i] != p[j])j = pmt[j - 1];if (p[i] == p[j])j++;pmt[i] = j;}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n;cin >> n;string str;cin >> str;get_pmt(str);ll ans = 0;for (int i = 2, j = 2;i <= str.size();i++, j = i) {while (pmt[j - 1])j = pmt[j - 1];if (pmt[i - 1])pmt[i - 1] = j;ans += i - j;}cout << ans;return 0;
}

这篇关于洛谷p3435 OKR-Periods of Words的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---