【2018SCUACM Wednesday 3 String】

题目来源

A:HDU 1711

B:HDU 1686

C:HDU 2087

D:HDU 3746

E:POJ 2406

F:HDU 2222

G:HDU 2457

H:HDU 4057

解题报告

A:裸的KMP字符串匹配,输出最早出现位置,个人习惯字符串从0编号,所以答案+1

B:使用KMP算法来寻找可重复子串P个数,对标准KMP稍作修改即可。

C:使用KMP算法来计算不可重复子串P数目个数,与B题代码仅略有不同,这种题区分点都在匹配完成时。

D:KMP的Next数组的应用。\(len-next[len]\)就是字符串的循环节长度,如果字符串长度刚好是循环节长度的倍数且大于一倍,那不用加东西直接输出0,否则输出\(repeatLen-len\%repeatLen\),也就是计算还要填多少个珠子才能把最后一个循环节构造完。

另外,这道题用memset会WA!太真实了……

 

E:使用非优化的\(next\)数组求法,则\(next[len]\)就是整个字符串最大前缀后缀数,则\(len-next[len]\)即为循环节长度,若其能被\(len\)整除,则输出\(\frac{len}{repeatLen}\),否则就是像\(abc\)或\(abddab\)这样的字符串,输出\(1\)即可。

F:AC自动机模板题,注意题意是统计给定的关键词集合(可能有重复关键词)中有多少关键词出现过,不是文章中出现了多少次关键词,比如:

1
3
it
it
she
its

这组数据应该输出2而不是1(文章”its”匹配到关键词”it”,这个关键词一共有两个)。

下面的代码用的是最初级的AC自动机,目的是更加直白的理解AC自动机,优化版AC自动机见:

HDU 2222 Keywords Search

G:AC自动机+DP。设\(dp[i][j]\)表示字符串走到位置\(i\)(位置从\(0\)开始编号),且自动机走到结点\(j\)时所需的最少修改方案。构造自动机时,记录是单词末尾的节点,这些节点显然不能走。换位思考,意思不就是除了这些节点之外都是安全节点了嘛~所以我们从零开始构造一个字符串,把原字符串放到AC自动机里跑,如果这个节点是安全节点,而原串位置\(i\)的字符与节点\(j\)的字符不一样,那就要将原串的字符修改为\(j\)结点的字符,从而确保构造出来的字符串是合法的。所以不难得出状态转移方程式:\(dp[i+1][Next]=min(dp[i+1][Next],dp[i][j]+(str[i]==char[node[j]]?0:1)\)。

值得一提的是,构造\(fail\)指针时,如果一个存在的节点指向的\(fail\)节点是一个危险节点,那么这个节点也是危险节点。举例:比如有一个单词\(she\),还有一个单词\(he\),\(she\)的\(e\)指向的是\(he\)中的\(e\),若\(he\)是危险的,则显然\(she\)也是危险的。

所以在转移之前,我们首先判断\(dp[i][j]\)是不是能走到的节点,如果不是直接跳过;如果是,再考虑\(j\)的儿子\(Next\)是不是危险节点,如果是,同样跳过;否则用上述转移方程式进行转移。

由于\(dp[i][j]\)表示的是“走到位置\(i\)”,所以处理到\(i\)时实际上并不包括\(i\)本身,于是最终答案是\(min(dp[len][0])\)而不是\(min(dp[len-1][0])\),最后判断一下不可能的情况输出\(-1\)就行了。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*