洛谷p4391 无限传输

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

考察字符串周期的题
题目链接

结论

要求字串$s$的最短循环字串长就是：$ans=n-pmt[n]$
证明如下：
这是最大的前缀和后缀
现在我们做如下操作：

补全字段$a$和字段$b$，按子段$a$的长度人为分开并标号
上下对应相等，所以1等于a
因为公共前后缀，所以1等于7
…
所以红色字段是最大循环字串

ACcode

#include<bits/stdc++.h>using namespace std;const int M = 1e6 + 9;
int 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);int n;cin >> n;string str;cin >> str;get_pmt(str);cout << n - pmt[n - 1];return 0;
}

这篇关于洛谷p4391 无限传输的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---