时雨小径 May the Spirit be with you

两个字符串题目

这个学期实在是太酷毙苦逼了,第一次有这种用尽全力还是跟不上的感觉,要是人活着可以不用睡觉就好了…
天天读paper,做证明题,还有什么3DFFT,并行矩阵乘法…简直是…唉,将来找工作又能用到多少呢,还不如多刷几个算法题…

记一下这星期做的两个算法题,顺便测试下$\LaTeX$插件.

  1. 说的是给一个字符串,$S = {a,b,c}^n, n \leq 100$,相邻的两个字符可以转化成另一个字符,直到不能转化为止,比如"ac"=>"b","acc"=>"bc"=>"a",求可以通过转化达到的最短长度.

想了下贪心,没什么把握,就DP了, 容易想到的是,如果初始字符串不是只含有一种字符,那么最后的结果最多为2,证明挺简单的.然后还有一个直观的就是最短的字符串一定是只含一种字符的.接下来就是dp方程:
设$\mathcal{K} = {a,b,c}, k \in \mathcal{K}$, $f(i , j , k)$ 表示从$i$到$j$这段字符串通过转化,成为只含有字符$k$的字符串的最短长度.于是$f(i , j , k)$ 可以从 $f(i + 1 , j , \mathcal{K})$ , $f(i , j - 1 , \mathcal{K})$ 以及 $f(i + 1 , j - 1 , \mathcal{K})$ 转移过来, 其中还得注意长度奇偶性什么的.Anyway,写得很麻烦,好歹过了…

  1. 还是字符串的题目,给个字符串$S = {a,b,…,z}^n , n \leq 100000$, 要求所有后缀与$S$的公共前缀和.

一开始是想用KMP的思想来做的, 主要是看见KMP里有匹配前缀的过程,$a[1,j] = a[i- j + 1 ,i]$, 后来发现不行,于是用后缀数组搞定了.做法是求出后缀数组和高度数组后,找到$S$在后缀数组中的位置$p$,然后往两边遍历一下.

话说这个$\LaTeX$插件还真的不错,叫做QuickLatex,话说自从用了$\LaTeX$之后, 虽然写作业的速度慢了点,但是看起来的确是专业了不少啊!