专题: 处理字符串题的思维方式

目录

• 前言
• 各种思维方式
• 数数型
• 决策型
• 匹配型
• → To Be Continued...

字符串题大致分成几种类型：

1. 数满足条件的字符串数
2. 与dp，贪心等决策相结合
3. 匹配，或者判断一个串是否满足某条件

前言

这里说的多数定义都不太严谨，都会用“类似”“长成...样”一类语言表达

各种思维方式

1. 对于“子串”类的问题，我们可以固定一个端点，考虑另一个端点的变化数

2. 传统字符串题更多地关注字符串在数据结构上的表现

   因此，我们可以适当的考虑一些处理字符串的结构，并结合这些结构考虑我们应该怎么做

数数型

数满足条件的字符串数。

1. 一个重要的性质是“包含关系”，长成这样：

   对于一个串，如果它满足条件，那么它的子串也满足条件；另一种类似的是，如果一个串满足，那么它的“父串”也满足。

   对于这样的问题，我们可以维护出某个位置结束/开始，或者是SAM上的一个节点，最长/最短满足条件的长度，然后加起来，数出满足条件的

   例：[NOI2018] 你的名字 —— 跑一遍匹配之后，考虑SAM内的每个节点，去除掉长度<=最长匹配的那些，剩下数一数就行

2. 遇到“本质不同”，先考虑SAM

决策型

1. 一个方法是，先想对策，然后用SA/SAM等工具来优化这个过程中的一些东西。

   例： [BJOI2015]隐身术 —— 用SA求LCP，来优化dp的过程

   例2：CF461E Appleman and a Game —— 用Trie来求出转移矩阵（当然这个题重点不在字符串这）

2. 当然，也可以直接在结构上考虑决策，比如涉及字典序可以考虑SA

匹配型

（我目前见到的）这种题一般比较板子，比如 [HEOI2015]最短不公共子串，顶多建上几个自动机就完事了

→ To Be Continued...

可以有更多分类，更多的思维方式，我暂时还不太会