洛谷P4391 [BOI2009]Radio Transmission 无线传输——题解
2024-09-05 19:33:15
假如我们有一个用于循环连接的最短串ans，考虑用它造出来的数据（即输入的字符串s）有什么特点。发现：ans自我连接出一个大串z后从中取出的一个子串即为s，对s造一个KMP算法中的next数组，n-next[n]即为ans的长度（n为字符串s的长度）。
为什么？因为ans在s串中开头的那个字母一定会多次作为ans中的同一部分（或说同一位置）出现（否则s串就要比ans还要短（自己从纸上写个串就知道了），那么它自己就比ans更优（更短）了（这时让s串自己作为答案都要比让ans作为答案更优），显然不合理），设s[0]在ans中的正确位置（在z取出s前的那个ans循环节中的位置）为j，那么造next[n]的时候s串自我匹配时s[0]匹配到的一定是s串中紧接着下一个在ans中位置为j的字母c。设c在s串中的位置为w，那么s串w位置往后的所有字母都会被匹配到（因为s串是一个由循环子串组成的串的子串）。此时n-next[n]就是s[0]到c的之间（左闭右开）的字符串a的长度。显然因为c是s[0]在s串中紧接着下一个在ans中位置为j的字母，所以s[0]和c之间隔着的字符串的长度就是ans的长度。
代码很好写，只要按照KMP算法的模板处理出next[n]，输出n-next[n]就行了，这里不多赘述。
最新文章
- centos6.8服务器部署svn
- C#线程通信与异步委托
- 转-sketch技巧
- Foj1675数论
- Sprite Kit编程指南（1）-深入Sprite Kit
- Python学习笔记_Chapter 7web开发
- ubuntu16.04 英文环境安装google chrome
- 在windows下使用cmd命令全速下载百度云文件
- python学习：常量和变量
- python的partial()用法说明
- 关于Android的Service知识点，你知道吗？
- linux ntp 时间同步
- PHP数组（数组正则表达式、数组、预定义数组）
- kali漏洞扫描
- 在MacOSX系统上的一些工具和问题汇总
- 2017 清北济南考前刷题Day 5 afternoon
- hadoop安装及注意事项
- wpf下使用NotifyIcon
- 概要梳理kafka知识点
- attribute用法