Cur1ed

KMP&拓展KMP

ac自动机(12) cf(1) 后缀数组(21) 回文串(2) 图论(9) 字典树(6) 字符串(2) 未归档(87) 计算几何(1) 计算机网络实验(1) 题解(29)

/ 注册

全部文章 / KMP&拓展KMP （共22篇）

匹配统计

传送门：https://www.acwing.com/problem/content/162/（acwing有视频讲解，题解，数据之类的）题意：给你两个字符串a和b，有q次询问，每次询问输出a的所有后缀和b恰好匹配长度为x的后缀个数。题解：这个题好微妙啊，我换了两种思路都不太对。然后看了一下...

2020-07-11

0 515

POJ - 3376 Finding Palindromes（拓展kmp+trie）

传送门：POJ - 3376 题意：给你n个字符串，两两结合，问有多少个是回文的；题解：这个题真的恶心，我直接经历了5种错误类型 : ) ... 因为卡内存，所以又把字典树改成了指针版本的。字符串s与字符串t组合是回文串的情况 1. len(s) > len(t), t的反串是 s...

2020-03-29

0 453

POJ - 3376 Finding Palindromes（拓展kmp+trie）

传送门：POJ - 3376 题意：给你n个字符串，两两结合，问有多少个是回文的；题解：这个题真的恶心，我直接经历了5种错误类型 : ) ... 因为卡内存，所以又把字典树改成了指针版本的。字符串s与字符串t组合是回文串的情况 1. len(s) > len(t), t的反串是 s...

2020-03-29

0 546

POJ - 3376 Finding Palindromes（拓展kmp+trie）

传送门：POJ - 3376 题意：给你n个字符串，两两结合，问有多少个是回文的；题解：这个题真的恶心，我直接经历了5种错误类型 : ) ... 因为卡内存，所以又把字典树改成了指针版本的。字符串s与字符串t组合是回文串的情况 1. len(s) > len(t), t的反串是 s...

2020-03-29

0 409

FZU - 1901 Period II （kmp）

传送门：FZU - 1901 题意：给你个字符串，让你求有多少个p可以使S[i]==S[i+P] (0<=i<len-p-1)。题解：这个题是真的坑，一开始怎么都觉得自己不可能错，然后看了别人的博客打脸了，发现自己掉坑了了...一开始想的是找出最小循环节，只要每次输出多加一个循环节...

2020-03-28

0 418

FZU - 1901 Period II （kmp）

传送门：FZU - 1901 题意：给你个字符串，让你求有多少个p可以使S[i]==S[i+P] (0<=i<len-p-1)。题解：这个题是真的坑，一开始怎么都觉得自己不可能错，然后看了别人的博客打脸了，发现自己掉坑了了...一开始想的是找出最小循环节，只要每次输出多加一个循环节...

2020-03-28

0 622

FZU - 1901 Period II （kmp）

传送门：FZU - 1901 题意：给你个字符串，让你求有多少个p可以使S[i]==S[i+P] (0<=i<len-p-1)。题解：这个题是真的坑，一开始怎么都觉得自己不可能错，然后看了别人的博客打脸了，发现自己掉坑了了...一开始想的是找出最小循环节，只要每次输出多加一个循环节...

2020-03-28

0 447

HDU - 3613 Best Reward（manacher或拓展kmp）

传送门：HDU - 3613 题意：给出26个字母的价值，然后给你一个字符串，把它分成两个字符串，字符串是回文串才算价值，求价值最大是多少。题解：这个题可以用马拉车，也可以用拓展kmp。 ①Manacher：先记录下第i个字符的价值，然后求前缀和。然后遍历分的位置，分别判断前半段和后半段是...

2020-03-27

0 513

HDU - 3613 Best Reward（manacher或拓展kmp）

传送门：HDU - 3613 题意：给出26个字母的价值，然后给你一个字符串，把它分成两个字符串，字符串是回文串才算价值，求价值最大是多少。题解：这个题可以用马拉车，也可以用拓展kmp。 ①Manacher：先记录下第i个字符的价值，然后求前缀和。然后遍历分的位置，分别判断前半段和后半段是...

2020-03-27

0 423

HDU - 3613 Best Reward（manacher或拓展kmp）

传送门：HDU - 3613 题意：给出26个字母的价值，然后给你一个字符串，把它分成两个字符串，字符串是回文串才算价值，求价值最大是多少。题解：这个题可以用马拉车，也可以用拓展kmp。 ①Manacher：先记录下第i个字符的价值，然后求前缀和。然后遍历分的位置，分别判断前半段和后半段是...

2020-03-27

0 387