第九章

# [返回目录](https://www.luogu.com.cn/training/441063) ## 9.1 进制哈希 ### 例9.1 [【模板】字符串哈希](https://www.luogu.com.cn/problem/P3370) ### 例9.2 [[POI2010] ANT-Antisymmetry](https://www.luogu.com.cn/problem/P3501) ### 例9.3 [[BOI2009] Radio Transmission 无线传输](https://www.luogu.com.cn/problem/P4391) #### 课后习题: [P5270 无论怎样神树大人都会删库跑路](https://www.luogu.com.cn/problem/P5270) [P5537 【XR-3】系统设计](https://www.luogu.com.cn/problem/P5537) [hdu 4821 String](https://acm.hdu.edu.cn/showproblem.php?pid=4821) [hdu 4080 Stammering Aliens](https://acm.hdu.edu.cn/showproblem.php?pid=4080) [hdu 4622 Reincarnation](https://acm.hdu.edu.cn/showproblem.php?pid=4622) ## 9.2 Manacher ### 例9.4 [【模板】manacher](https://www.luogu.com.cn/problem/P3805) #### 课后习题: [P1659 [国家集训队] 拉拉队排练](https://www.luogu.com.cn/problem/P1659) [P4555 [国家集训队] 最长双回文串](https://www.luogu.com.cn/problem/P4555) [hdu 3294 Girls' research](https://acm.hdu.edu.cn/showproblem.php?pid=3294) ## 9.3 字典树 ### 例9.5 [于是他错误的点名开始了](https://www.luogu.com.cn/problem/P2580) #### 课后习题: [P3879 [TJOI2010] 阅读理解](https://www.luogu.com.cn/problem/P3879) [P2292 [HNOI2004] L 语言](https://www.luogu.com.cn/problem/P2292) [P2922 [USACO08DEC] Secret Message G](https://www.luogu.com.cn/problem/P2922) [P3065 [USACO12DEC] First! G](https://www.luogu.com.cn/problem/P3065) [P3294 [SCOI2016] 背单词](https://www.luogu.com.cn/problem/P3294) [P4407 [JSOI2009] 电子字典](https://www.luogu.com.cn/problem/P4407) [P4551 最长异或路径](https://www.luogu.com.cn/problem/P4551) [P4683 [IOI2008] Type Printer](https://www.luogu.com.cn/problem/P4683) [P3783 [SDOI2017] 天才黑客](https://www.luogu.com.cn/problem/P3783) ## 9.4 回文树 ### 例9.6 [Victor and String](https://acm.hdu.edu.cn/showproblem.php?pid=5421) #### 课后习题: [P5496 【模板】回文自动机（PAM）](https://www.luogu.com.cn/problem/P5496) [P3649 [APIO2014] 回文串](https://www.luogu.com.cn/problem/P3649) [P4287 [SHOI2011] 双倍回文](https://www.luogu.com.cn/problem/P4287) [P4762 [CERC2014] Virus synthesis](https://www.luogu.com.cn/problem/P4762) ## 9.5 KMP ### 例9.7 [剪花布条](https://acm.hdu.edu.cn/showproblem.php?pid=2087) ### 例9.8 [[BOI2009] Radio Transmission 无线传输](https://www.luogu.com.cn/problem/P4391) ### 例9.9 [[USACO15FEB] Censoring S](https://www.luogu.com.cn/problem/P4824) ### 例9.10 [【模板】扩展 KMP/exKMP（Z 函数）](https://www.luogu.com.cn/problem/P5410) #### 课后习题: [hdu 1686 Oulipo](https://acm.hdu.edu.cn/showproblem.php?pid=1686) [hdu 1711 Number Sequence](https://acm.hdu.edu.cn/showproblem.php?pid=1711) [hdu 2222 Keywords Search](https://acm.hdu.edu.cn/showproblem.php?pid=2222) [hdu 2896 病毒侵袭](https://acm.hdu.edu.cn/showproblem.php?pid=2896) [hdu 3065 病毒侵袭持续中](https://acm.hdu.edu.cn/showproblem.php?pid=3065) [hdu 3336 Count the string](https://acm.hdu.edu.cn/showproblem.php?pid=3336) [hdu 2594 Simpsons’ Hidden Talents](https://acm.hdu.edu.cn/showproblem.php?pid=2594) [poj 1961 Period](http://poj.org/problem?id=1961) [poj 2406 Power Strings](http://poj.org/problem?id=2406) [P3375 【模板】KMP](https://www.luogu.com.cn/problem/P3375) [P3435 [POI2006] OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) [P2375 [NOI2014] 动物园](https://www.luogu.com.cn/problem/P2375) [P3426 [POI2005] SZA-Template](https://www.luogu.com.cn/problem/P3426) [P3193 [HNOI2008] GT考试](https://www.luogu.com.cn/problem/P3193) ## 9.6 AC自动机 ### 例9.11 [Keywords Search](https://acm.hdu.edu.cn/showproblem.php?pid=2222) #### 课后习题: [hdu 2243 考研路茫茫——单词情结](https://acm.hdu.edu.cn/showproblem.php?pid=2243) [hdu 2825 Wireless Password](https://acm.hdu.edu.cn/showproblem.php?pid=2825) [hdu 2296 Ring](https://acm.hdu.edu.cn/showproblem.php?pid=2296) [hdu 3341 Lost's revenge](https://acm.hdu.edu.cn/showproblem.php?pid=3341) [hdu 4758 Walk Through Squares](https://acm.hdu.edu.cn/showproblem.php?pid=4758) [P3808 【模板】AC 自动机（简单版）](https://www.luogu.com.cn/problem/P3808) [P3796 【模板】AC 自动机（加强版）](https://www.luogu.com.cn/problem/P3796) [P5357 【模板】AC 自动机（二次加强版）](https://www.luogu.com.cn/problem/P5357) [P2414 [NOI2011] 阿狸的打字机](https://www.luogu.com.cn/problem/P2414) [P3966 [TJOI2013] 单词](https://www.luogu.com.cn/problem/P3966) [P3311 [SDOI2014] 数数](https://www.luogu.com.cn/problem/P3311) [P4052 [JSOI2007] 文本生成器](https://www.luogu.com.cn/problem/P4052) [P5599 【XR-4】文本编辑器](https://www.luogu.com.cn/problem/P5599) [P3121 [USACO15FEB] Censoring G](https://www.luogu.com.cn/problem/P3121) [P2444 [POI2000] 病毒](https://www.luogu.com.cn/problem/P2444) ## 9.7 后缀树和后缀数组 ### 例9.12 [Longest Common Substring](https://acm.hdu.edu.cn/showproblem.php?pid=1403) #### 课后习题: [hdu 5769 Substring](https://acm.hdu.edu.cn/showproblem.php?pid=5769) [hdu 3948 The Number of Palindromes](https://acm.hdu.edu.cn/showproblem.php?pid=3948) [hdu 4591 Math Homework](https://acm.hdu.edu.cn/showproblem.php?pid=4591) [hdu 5008 Boring String Problem](https://acm.hdu.edu.cn/showproblem.php?pid=5008) [P3809 【模板】后缀排序](https://www.luogu.com.cn/problem/P3809) [P5353 树上后缀排序](https://www.luogu.com.cn/problem/P5353) [P2336 [SCOI2012] 喵星球上的点名](https://www.luogu.com.cn/problem/P2336) [P2463 [SDOI2008] Sandy 的卡片](https://www.luogu.com.cn/problem/P2463) [P2852 [USACO06DEC] Milk Patterns G](https://www.luogu.com.cn/problem/P2852) [P4051 [JSOI2007] 字符加密](https://www.luogu.com.cn/problem/P4051) [P1117 [NOI2016] 优秀的拆分](https://www.luogu.com.cn/problem/P1117) [P2178 [NOI2015] 品酒大会](https://www.luogu.com.cn/problem/P2178) [P5346 【XR-1】柯南家族](https://www.luogu.com.cn/problem/P5346) [P5576 [CmdOI2019] 口头禅](https://www.luogu.com.cn/problem/P5576) ## 9.8 后缀自动机 ### 例9.13 [Reincarnation](https://acm.hdu.edu.cn/showproblem.php?pid=4622) #### 课后习题: [P3804 【模板】后缀自动机（SAM）](https://www.luogu.com.cn/problem/P3804) [P3975 [TJOI2015] 弦论](https://www.luogu.com.cn/problem/P3975) [P4248 [AHOI2013] 差异](https://www.luogu.com.cn/problem/P4248) [P5341 [TJOI2019] 甲苯先生和大中锋的字符串](https://www.luogu.com.cn/problem/P5341) [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770) [P5284 [十二省联考 2019] 字符串问题](https://www.luogu.com.cn/problem/P5284) [P5319 [BJOI2019] 奥术神杖](https://www.luogu.com.cn/problem/P5319)