111qqz的小窝

老年咸鱼冲锋!

【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<

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

hdu 3374 题目链接 题意:给出一个循环字符串,问最小表示出现的位置以及次数,最大表示出现的位置以及次数。 思路:之前只写过最小表示。。最大表示其实是一

hdu 4300 Clairewd’s message (kmp)

hdu 4300题目链接 吐槽:题意难懂的一逼,关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。?本来挺傻逼一道

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

hdu 3336 题目链接 题意:给一个字符串,问这个字符串的所有前缀的出现次数的和。 思路:这道题需要完全理解nxt函数是干嘛的。。nxt[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。。。懒得说了。注意边界。 /* *********************************************** Author :111qqz Created Time :2016年08月12日 星期五 01

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

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

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

hdu 5763 题目链接 题意:给定两个字符串A和B,每个出现在A中的B(可以overlap)都有两种含义,问A串一共可能有多少种含义。 思路:kmp+dp

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

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

hdu 1841 Find the Shortest Common Superstring (kmp)

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

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

hdu 1358 题目链接 题意:给一个字符串,求这个字符串的每个前缀(包括本身)的能否由k个子串组成(K>1) 思路:和poj 2406 比较类似。。 结论:字符

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

hdu 2087 题目链接 题意:问模式串在文本串中出现的次数,不允许重叠。 思路:kmp,关键在于不允许重叠。。。 其实只要每次找到的时候j=0一下就好咯。 /*

hdu 1711 Number Sequence (kmp)

hdu 1711 题目链接 题意:给定两个数列,问第二个数列在第一个数列中出现的位置(第一个元素对应的位置) 思路:数列也可以看成字符串,然后左kmp,返回的

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

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

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

poj 2185 题目链接 题意:给出一个字符矩形,问一个面积最小的矩形,覆盖掉整个矩形。大概就是二维的最小覆盖子串。 思路:对于每一行做最小覆盖子串,然后求

KMP与最小覆盖子串

参考资料(本文大部分是参考这篇博客,附带一些证明步骤的解释) 首先明确一些概念: 最小覆盖子串:对于某个字符串s,它的最小覆盖子串指的是长度最小

poj 2752 Seek the Name, Seek the Fame (kmp 理解nxt函数)

poj 2752题目链接 题意:求出所有的前缀和后缀相同的子串的长度。 思路:求出nxt函数,观察发现,从从len递归向前就是答案。 /* *********************************************** Author :111qqz Created Time :20

hdu 1686 Oulipo (kmp模板题)

hdu1686 题意:给出模式串和文本串,问模式串在文本串中出现了多少次,可以overlap. 思路:思考naive的匹配过程。nxt函数不过是改进了当失配

KMP算法学习

20170801update:当时竟然没有强调next函数的含义? next[i]的含义是,i之前的整个前缀中,最长的该前缀的前缀和后缀相同的

poj 2406 Power Strings (后缀数组||kmp)

poj 2406 题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的, 求 R 的最大值 思路:论文题. 转载论文中的题解: 最关键的在加黑的那句