【dp专题001】bzoj 1009: [HNOI2008]GT考试 (字符串上dp+kmp+矩阵加速线性递推式)

 

1009: [HNOI2008]GT考试

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 3127  Solved: 1926
[Submit][Status][Discuss]

Description

  阿申准备报名参加GT考试,准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2…Am(0<=Ai<=9)有M位,不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为
0

Input

  第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

  阿申想知道不出现不吉利数字的号码有多少种,输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81

思路:

这次总算想对了状态表示:dp[i][j] 表示当前处理到第i位,最后j位与不吉利串相同的方案数。

然后此时考虑转移,也就是观察第i+1位。

根据第i+1位字符的不同,转移到的 位置也不相同。

从dp[i][j] 可以转移到dp[i+1][k],这种转移表现为dp[i+1][k] += dp[i][j] (k取决于第i+1位字符)

我们可以用f[i+1][k]+=f[i][j]*trans[j][k],trans[j][k]表示串s后j位与不吉利串前j位相同,

添加一个字符后后k位与不吉利串前k位相同的方案数。

%e9%80%89%e5%8c%ba_001

就是说中间的那一部式子可以化简成矩阵的形式。。因此整个递推式就成了矩阵乘法的形式。

tran数组可以用kmp预处理出来。

 

重点是注意体会在字符串上dp的思想。

 

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

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

 

 

 

hdu 4300 Clairewd’s message (kmp)

hdu 4300题目链接

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

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

然后给出一个字符串,先是密文再是明文,明文可能不全。问最小的可能的密文+明文串是什么。。

思路:

把字符串按照密码表转化得到一个新的字符串,然后跑kmp得到原字符串a的后缀等于转化后的字符串b的前缀的最长长度的字符串。(需要注意的是,kmp匹配的时候,由于密文长度一定是大于等于明文的,并且如果字符串a和字符串b相等,匹配全部是没有意义的,所以我们从中间位置开始匹配,更具体的说,是从第一个后面的字符串的长度大于等于前面的字符串的长度的位置开始匹配

 

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

hdu 3336 题目链接

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

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

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

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

s          a    b    a    b    a
i          0    1    2    3    4   5
next[i]     -1   0    0    1    2   3

ans初始为len(因为长度为len的字符串有len个前缀,每个前缀至少出现一次)
next[3] = 1,ans + 1 = 6,next[1] = 0
next[4] = 2,ans + 1 = 7,next[2] = 0
next[5] = 3,ans + 1 = 8,next[3] = 1,ans + 1 = 9

 

首先,我们不是很关心nxt[i]具体的值,只关心nxt[i]是否大于0.如果大于0,比如对于nxt[3]==1,说明字符串0..2位置中,存在一个后缀和前缀相等,因此答案+1.

其次,其实我们仍然关心nxt[i]具体的值,对于nxt[5]==3,具体对应的含义是有后缀“aba”和前缀“aba”相等

但是这就完了吗?因为nxt[3]仍然大于0,对应“aba”中有一个前缀”a“和后者”a“相等。。。你可能要问。。这个不是刚刚算过了吗。。。然而这里其实算的是字符串2..4的”aba”。

看到有人说这是dp…不是很懂dp做法是什么鬼。。。

忘记取模wa了一发。。智力-2.

 

 

下面补一个dp做法好了。

dp[i]表示长度为i的前缀出现的此处,显然每个前缀至少出现了一次,所以初始化dp[i]=1  (1=<i <= len)

转移方程为dp[nxt[i]] += dp[i];

这里还是涉及到nxt函数的含义

nxt[i]表示的是字符串的0..i-1位中,前缀和后缀相等的串的最长长度为nxt[i]

这就说明,对于长度为i的前缀,有一个长度为nxt[i]的前缀,出现在了该长度为i的前缀的后缀处。

后往前扫的原因是,对于长度为i的前缀,其长度为nxt[i]的前缀可能仍然有一个长度为nxt[nxt[i]]的前缀,

从后往前可以保证,当从len扫描到i时,已经将i+1~len的贡献累加到dp[i]

 

 

 

hdu 2594 Simpsons’ Hidden Talent (kmp)

hdu 2594 题目链接

题意:given string s1,s2, find the longest prefix of s1 that is a suffix of s2.

思路:kmp。。。懒得说了。注意边界。

 

 

 

 

 

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

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

思路:一下子想到了最小覆盖子串的模型。。。我求出最小覆盖子串的长度(n-nxt[n])。然后特判下最小覆盖子串的长度等于字符串长度的情况。。。试着叫了一发。。。竟然就A了2333.。。大概是所谓的题感吧(逃

 

 

 

 

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个字符对其他位置字符的贡献。

首先第i位的含义数可以无条件得转移到i+1位。也就是dp[i+1]+=dp[i];

此外,如果第i位是一个B串开始的位置,那么第i位对i+len2位就有贡献。也就是dp[i+len2]+=dp[i];

初始化dp[0]=1,其他为0.

剩下我们要做的就是处理出A串中的哪些位置是B串开始的位置。

kmp处理下就好,用一个布尔数组标记。

 

 

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

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

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

还要注意。。这道题要求了长度相同时按照字典序小的方法拼接。。。

 

 

hdu 1841 Find the Shortest Common Superstring (kmp)

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

 

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

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

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

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

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

 

upd:代码新添加了注释。

 

hdu 1358 Period (kmp,求字符串的周期)

hdu 1358 题目链接

题意:给一个字符串,求这个字符串的每个前缀(包括本身)的能否由k个子串组成(K>1)

思路:和poj 2406 比较类似。。

结论:字符编号从0开始,如果又i%(i-next[i])==0,则i前面的
串为一个轮回串,其中轮回子串出现i/(i-next[i])次。

证明类似之前最小覆盖中的,不断的等价交换,两两相等…(这个证明在字符串这里总是遇到2333)

然而其实我。。。做的时候。。并没有想到去证明。。。而是打印出了nxt数组然后找规律求得2333.

之前一直觉得找规律不是什么拿的上台面的做法。。。但是今年打了几场多校。。尤其是电子科大的那场。。。我发现。。。其实有的题目的正解就是找规律,猜结论。。。

 

 

 

&nbs

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

hdu 2087 题目链接

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

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

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

hdu 1711 Number Sequence (kmp)

hdu 1711 题目链接

题意:给定两个数列,问第二个数列在第一个数列中出现的位置(第一个元素对应的位置)

思路:数列也可以看成字符串,然后左kmp,返回的答案是i+1-m。。。1A

 

 

 

 

 

poj 3080 Blue Jeans (n个字符串的最长公共子串,暴力+kmp)

poj 3080 题目链接

题意:给出n个字符串(n<=10),字符串长度不超过70,问出现在全部n个字符串中的最长并且字典序最小的长度大于等于3的子串。

思路:数据范围很小。。。直接暴力枚举+kmp匹配一下。。。

 

poj 2185 Milking Grid (最小覆盖子矩形,kmp)

poj 2185 题目链接

题意:给出一个字符矩形,问一个面积最小的矩形,覆盖掉整个矩形。大概就是二维的最小覆盖子串。

思路:对于每一行做最小覆盖子串,然后求lcm,每一列也是如此。最后记得判断不能超过原有的n,m。

 

 

 

KMP与最小覆盖子串

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

 

pre[i](或next[i])的实质是串str[1..i]的最长且小于i的“相等前、后缀”分别为str[1..pre[i]](前缀)与str[(i-pre[i]+1)..i](后缀),通俗讲就是:使str[1..i]前k个字母与后k个字母相等的最大k值。

 

结论先行:最小覆盖子串(串尾多一小段时,用前缀覆盖)长度为n-next[n](n-pre[n]),其中n为串长,串的最后一位为为s[n-1].

 

证明分两部分:

1-长为n-next[n]的前缀必为覆盖子串。

当next[n]<n-next[n]时,如图a,长为next[n]的前缀A与长为next[n]的后缀B相等,故长为n-next[n]的前缀C必覆盖后缀B;

当next[n]>n-next[n]时,如图b,将原串X向后移n-next[n]个单位得到Y串,根据next的定义,知长为next[n]的后缀串A与长为前缀串B相等,X串中的长为n-next[n]的前缀C与Y串中的前缀D相等,而X串中的串E又与Y串中的D相等……可见X串中的长为n-next[n]的前缀C可覆盖全串(其实是一个不断的等价交换的过程,用同样的方法可以证明每两个相邻的相等,所以可以覆盖全串

 

2-长为n-next[n]的前缀是最短的。

如图c,串A是长为n-next[n]的前缀,串B是长为next[n]的后缀,假设存在长度小于n-next[n]的前缀C能覆盖全串,则将原串X截去前面一段C,得到新串Y,则Y必与原串长度大于next[n]的前缀相等,与next数组的定义(使str[1..i]前k个字母与后k个字母相等的最大k值。)矛盾。得证!有人问,为什么Y与原串长大于next[n]的前缀相等?由假设知原串的构成必为CCC……E(E为C的前缀),串Y的构成必为CC……E(比原串少一个C),懂了吧!