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

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

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

前言

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

各种思维方式

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

数数型

数满足条件的字符串数。

  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...

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

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

上一篇:September 2020 company internal technical training


下一篇:Pytorch 多分类问题