【技巧总结】——字符串

【技巧总结】——字符串

字符串

• h a s h hash hash
• • 解决冲突的方法
  • 二维 h a s h hash hash
  • 回文串判断
• K M P KMP KMP
• • 最小循环节
  • 最小表示法
  • 限制类
  • DP
• AC自动机（多串匹配）
• • DP

h a s h hash hash 解决冲突的方法

1. v e c t o r vector vector数组存储
   经典例题：集合的关系
2. 线性探测法（其实就是有冲突了就往后放）这里注意一定要把模数开大一点，不然处处碰壁
   经典例题：
   随机的点
   异或

二维 h a s h hash hash

也不知道是啥原理，公式比普通的字符串 h a s h hash hash长了不止一倍，麻了
经典例题：
M a t r i x Matrix Matrix（公式是真长）

回文串判断

先正着来一遍，再把字符串反转，正着来一遍
经典例题：
P a l i n d r o m e Palindrome Palindrome–回文子串的最大长度

K M P KMP KMP 最小循环节

n − n x t [ n ] n-nxt[n] n−nxt[n]
经典例题：
R a d i o T r a n s m i s s i o n Radio Transmission RadioTransmission 无线传输

M i l k i n g G r i d Milking Grid MilkingGrid（最小循环节+（字符串→字符））
本道题把一个字符串看成了一个字符，进行 k m p kmp kmp运算，思路很巧妙
O m N o m a n d N e c k l a c e Om Nom and Necklace OmNomandNecklace（与最小循环节有关的计算，有点涉及数学知识）

最小表示法

就是把一串字符当成环，然后找到字典序最小的那一个表示方法，可以判断一条环是否相同啊之类的
经典例题：
S n o w f l a k e S n o w S n o w f l a k e s Snowflake Snow Snowflakes SnowflakeSnowSnowflakes（这个可以暴力，因为每次只有6个点，但是形式上确实是最小表示法的模板）
N e c k l a c e Necklace Necklace（纯板子）

限制类

1. 要求前缀和后缀不重叠，也就是 n x t nxt nxt数组的值不超过字符串的一半
   预处理 n x t nxt nxt的时候直接板子，在计算结果的时候加限制即可，也就是让 j j j的值永远不超过 i / 2 i/2 i/2
   经典例题：
   动物园
2. 删除子串（栈）
   这个模型其实完完全全的是栈的基本模型，但是用栈的话复杂度太高，所以要 n x t nxt nxt配合，每当遇到一个完整的单词都删除，这里手写栈的优势就出来了，可以把删掉长度为 l e n len len的字符的 *** 作，变为 t o t − = l e n tot-=len tot−=len，这样O(1)解决删除。
   经典例题：
   C e n s o r i n g Censoring Censoring

DP

其实大部分dp的 *** 作都是利用求出的 n x t nxt nxt数组累加之类的（最常见的模型了）
总结一些 n x t nxt nxt数组的性质吧：

1. 求 n x t nxt nxt数组的时候可做前缀和。 例：动物园

AC自动机（多串匹配）

t r i e trie trie树和 k m p kmp kmp算法的结合体，板子比较长，但是写着写着也就会了

DP

1. 不出现子串型
   DP格式都是三层循环，第一层枚举“文章”的长度，第二层枚举节点，第三层枚举“字母”，接着进行转移
   经典例题：
   修复DNA
   文本生成器（虽然要求至少出现一个子串，但是这和所有子串都不出现是对立事件啊，所以总数一减就ok了【滑稽】）