串相关模型

最难的算法在字符串…真的

首先基本功就是要对sring和char[]都得熟练操作

string的常用api 常用功能

char[]就是和数组一样了不过要额外注意一个'\0'的问题用法和双指针关联很大

回文问题

回文串的长度用中心扩展算法把每个位置都视为潜在的回文中心向两边拓展虽然回文中心分奇偶两种情况但无伤大雅可以把每个位置奇偶都做一遍如果不满足很快就会返回蛮暴力的其实可以用字符串哈希+二分做一个优化

回文匹配判断一个字符串是否可以由另一个字符串循环拼接得到比较常规的思路是拼接一份然后在长的里面find短的还有一个思路就是把两个串都用最小表示法表示出来如果相等就说明是可以循环拼接得到的

字符串匹配算法有很多

用什么题目很容易看得出来考察的就是这些算法的理解利用它的某个步骤的性质去做一些事情

对于很裸的匹配其实直接用find就行

考察kmp很多都是变形比如kmp 匹配时是原串和模式串双指针的匹配所以可以对一个原串匹配多次模式串（包含多个）然后就是核心next数组利用i ne[i]的特性可以得到i/(i-ne[i])若能整除 i-ne[i]就是当前的唯一最小循环结再或者利用回溯舍去前缀和交集部分得到不重叠前后缀的数量等等一切都基于算法本身所以对于字符串的题要用什么算法其实很容易看得出来

trie字典树的匹配过程是将字符串按每个字符的顺序插在树里面所以如果两个串存在公共前缀部分也就很容易找的出来（还有一个特点就是因为它的过程要做映射所以给的字符串一般都是全大写或全小写或全数字这样才能通过-'a' -'A' -'0'做到映射当然非要混合也不是不行这样就很麻烦了）（如果要把所有子串求出来放trie树里面再判断是否出现过不如直接把每个子串作为key 存在unordered_map里省事得多）

kmp+trie=ac自动机这个留以后学 b组省赛大概率用不到

最后就是字符串哈希它用途比较广泛不像kmp、trie那么具有鲜明特色（循环结、多次匹配、前缀匹配）要说有非他不能解决的问题那就是截取两段区间问是否相等这样的问题它的实现方式本质上是会有冲突的只不过通过一些经验值（131 13331 \(2^{64}\)) 使得它能在大多数情况下不会发生冲突用它解决问题的话可以不用想太多直接当做是可行的如果两串字符串最后的哈希值不一样就认为是不同的直接水掉所以它这种匹配方式很方便可以解决大多数问题又因为它这种相当于两个值匹配的方式很灵活就又可以和很多其他算法相结合比如二分

字符串排序后有一个特点有直接前缀关系的两个串一定是相邻的

串相关模型

串相关模型

基本操作

最小表示法

KMP

字典树

AC自动机

字符串哈希

💬 评论