111qqz的小窝

老年咸鱼冲锋!

hdu 1841 Find the Shortest Common Superstring (kmp)

hdu 1841题目链接
题意:给两个字符串,问包含这两个字符串的最小的字符串的长度(最小是因为,一个串的子串可能是另一个串的后缀,这样出现一次就可以了)

 

思路:其实这道题最关键的思想部分是和kmp没有关系的。。。

我们考虑最naive的匹配方式。

如果存在文本串的子串(之前写成了后缀,特此更正,不一定是首尾拼接,这是和hdu 1867的区别)等于模式串的前缀,那么这段子串或者后缀的长度为最后的j。

两个串各做一次模式串和文本串。

不过暴力匹配复杂度爆炸,所以用了kmp。。。

 

upd:代码新添加了注释。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz