cf432 D. Prefixes and Suffixes
2022/4/1 6:21:10
本文主要是介绍cf432 D. Prefixes and Suffixes,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
输出所有的 \(len\),使得给定字符串的长度为 \(len\) 的前缀与长度为 \(len\) 的后缀相等;并输出每个这种前缀在整个串中(作为子串)的出现次数。
思路:
前缀后缀啥的显然是 kmp 的 next 数组。初始 len=n,不断让 len=next[len] 就能找出所有的 len
重点是它们的出现次数怎么求。对于某段 \(s[1,len]\),它有可能在这些情况出现:
-
首先它本身出现一次,\(f(len)=1\)
-
作为某个位置 \(i\) 的 \(next\) 前缀,\(f(len=ne[i])+=f(i)\)
-
作为某个位置 \(i\) 的 \(next\) 的 \(next\),\(f(len=ne[ne[i]])+=f(i)\)
可以继续套娃。那么应该倒序dp
signed main() { iofast; cin >> s + 1; n = strlen(s + 1); //getNext for(int i = 2, j = 0; i <= n; i++) { while(j && s[i] != s[j+1]) j = ne[j]; if(s[i] == s[j+1]) j++; ne[i] = j; } fill(f + 1, f + 1 + n, 1); //dp for(int i = n; i; i--) f[ne[i]] += f[i]; vector<int> ans; //要求从小到大输出len for(int i = n; i; i = ne[i]) ans.pb(i); reverse(all(ans)); cout << ans.size() << endl; for(int i : ans) cout << i << ' ' << f[i] << endl; }
这篇关于cf432 D. Prefixes and Suffixes的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升