浅谈一类字符串问题

PDF以及配套数据下载地址：[难题选讲1-送你一序列字符串-Rockdu.rar](http://leanote.com/api/file/getAttach?fileId=5a6411deab64416d1c000771)
# 浅谈一类字符串问题
引言：有一类不常规的序列上字符串问题十分的特别。下面我们来看一个例子。

# <center>所有公共子序列问题V2</center>

## 时空限制：1s/256MB
### 题目描述：
给定长度分别为n, m的只包含小写字母的串A, B。你需要输出A、B所有本质不同的公共(或公共回文)子序列的个数，答案对66662333取模。详见数据范围。（空序列算作回文序列）
### 输入格式：
一行n, m, k, k作为子问题标识
第二行长度为n的字符串，表示A
另一行长度为m的字符串，表示B
### 输出格式：
一行表示答案
###样例输入1：
6 6 2
abbbcb
ccabcc
###样例输出1：
4
###样例输入2：
6 6 1
abbbcb
ccabcc
###样例输出2：
9
### 数据范围与子问题：
k = 1时只需要输出所有公共子序列的个数
k = 2时需要输出所有公共回文子序列的个数
对于前20%的数据1 <= n, m <= 10, k = 2
对于另外20%的数据n <= 1000000，m <= 20，k = 1
对于另外20%的数据n <= 1000000，m <= 20，k = 2
对于另外40%的数据1 <= n, m <= 3010， k = 1
对于100%的数据 n <= 1000000, m <= 3010
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
# 思考时间 |BGM: 
# ♫ Love Is in Bloom ——Daniel Ingram/My Little Pony
# ♫ Lullaby for a Princess ——Ponyphonic/Alex376 Cover
# ♫ Frozen Heart ——Frozen Night
$\space$
$\space$
$\space$
$\space$
$\space$ 
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$ 
$\space$

----------
在看正解之前，我们先来看一个小Trick：
对于一个字符串，我们建立这样一个DAG：
![图片标题](https://leanote.com/api/file/getImage?fileId=5a629925ab644112c40003a0)
对于每一个位置，我们拆出字符集大小个点，表示字符集中的字符。每一条代表字符x的点，向当前位置之后的子串中，字符x第一次出现的位置连一条边。对开头我们也处理成一个点，并拆出26个点。注意到，不难证明，这样连边之后我们从开头出发，每一条路径对应了一个子序列！

例如：序列acbc：
![图片标题](https://leanote.com/api/file/getImage?fileId=5a629ac2ab644112c40003c4)

但是有什么好处呢？

不难发现这样的话，我们检查一个字符串是否为一个串的子序列就可以做到$O(n\theta)^*(\theta:$字符集大小) 预处理，$O(m)$查询，而原来我们需要$O(n + m)$查询。

发现由于提高了每一个点的利用率，空间复杂度、边数和总状态数仍然为$O(n\theta)$。又因为在上面遍历节点可以遍历所有的子序列，有类似后缀自动机的性质。于是我们美其名曰:序列自动机。

现在知道了这个小小的trick，前面那道题是不是变成了水题了呀？

k = 1时，我们在两张图上记忆化搜索$dp[i][j]$表示第一张图在i点第二张图在j点，这样dp不会有本质相同的子序列被计算。注意到总状态为n * m的，那么我们dp的复杂度为$O(n * m)$

k = 2时，注意到必定有一个串长为20，如果没有本质不同的限制，我们$2^{20}$枚举它的子序列，每次再用$O(20)$判断是否为回文序列就可以水过去了，现在有了，我们只需要再建一棵trie树判断是否有重复子串就行了。

AC代码？要不自己脑补？$tan(90^o)$的
![图片标题](https://leanote.com/api/file/getImage?fileId=5a635317ab644112c40013dd)

没错，题目选讲怎么可能没有代码呢？这是$tan(90^o)$的。
不仅有代码，还有配套数据！详见目录下string文件夹。
代码其实很短，有兴趣的同学不妨手动写一写吧！

Rockdu's Blog

导航

最近发表

大佬们的友链