hdu 3374 String Problem (字符串的最小/大表示法+kmp)

hdu 3374 题目链接
题意:给出一个循环字符串,问最小表示出现的位置以及次数,最大表示出现的位置以及次数。
思路:之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[[……]

Read more

hdu 4300 Clairewd’s message (kmp)

hdu 4300题目链接

吐槽:题意难懂的一逼,关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。?本来挺傻逼一道题。。被这完全没有说清楚的题意搞得很不爽。。。

题意:给一个26个字母一一对应的密码表。

然后给出一个字符串,先是密文再是明文,明文可[……]

Read more

hdu 3336 Count the string (nxt函数的运用kmp+(dfs|dp ))

hdu 3336 题目链接

题意:给一个字符串,问这个字符串的所有前缀的出现次数的和。

思路:这道题需要完全理解nxt函数是干嘛的。。nxt[i]表示的是字符串的0..i-1位中,前缀和后缀相等的串的最长长度为nxt[i]

这东西对于这道题有什么用呢?

举个例子,对于字符串ababa:

s[……]

Read more

hdu 3746 Cyclic Nacklace (最小覆盖子串,kmp)

hdu 3746题目链接
题意:给定一个字符串,是一个环(首尾相连),问至少再添加多少个珠子才能使得整个串是循环的。。。

思路:一下子想到了最小覆盖子串的模型。。。我求出最小覆盖子串的长度(n-nxt[n])。然后特判下最小覆盖子串的长度等于字符串长度的情况。。。试着叫了一发。。。竟然就A了[……]

Read more

hdu 5763 || 2016 multi #4 1001 Another Meaning (kmp+dp)

hdu 5763 题目链接

题意:给定两个字符串A和B,每个出现在A中的B(可以overlap)都有两种含义,问A串一共可能有多少种含义。

思路:kmp+dp.

考虑dp[i]为前i个字符(也就是从开始长度为i,注意不是字符串的下标为i)的含义数。

我们考虑第i个字符对其他位[……]

Read more

hdu 1867 A + B for you again (kmp,最短的字符串a+b)

hdu 1867 题意
题意:给两个字符串,将两个字符串首尾拼接之后得到一个长度最短的字符串,求这个最短的字符串(一个串的前缀可能是另一个串的后缀,这样的话只出现一次就行了)

思路:kmp。。注意和hdu 1841区分。那道题是只要得到一个串包含两个串即可。这道题是首尾拼接得到。

还要[……]

Read more

hdu 1841 Find the Shortest Common Superstring (kmp)

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

 

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

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

如果存在文[……]

Read more

hdu 2087 剪花布条 (kmp,不允许重叠的匹配)

hdu 2087 题目链接

题意:问模式串在文本串中出现的次数,不允许重叠。

思路:kmp,关键在于不允许重叠。。。

其实只要每次找到的时候j=0一下就好咯。

KMP与最小覆盖子串

参考资料(本文大部分是参考这篇博客,附带一些证明步骤的解释)
首先明确一些概念:
最小覆盖子串:对于某个字符串s,它的最小覆盖子串指的是长度最小的子串p,p满足通过自身的多次连接得到q,最后能够使s成为q的子串。
比如:
对于s=”abcab”,它的最小覆盖子串p=”abc”,因为p通过在它[……]

Read more