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

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

hdu 4300题目链接

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

hdu 3336 题目链接

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

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

hdu 2594 题目链接

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

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

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月12日 星期五 01时12分51秒
 4File Name :code/hdu/2594.cpp
 5************************************************ */
 6#include …

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

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

hdu 5763 题目链接

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

思路：kmp+dp.

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

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

hdu 1358 题目链接

题意：给一个字符串，求这个字符串的每个前缀（包括本身）的能否由k个子串组成（K>1）

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

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

hdu 2087 题目链接

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

思路：kmp，关键在于不允许重叠。。。

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

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月11日 星期四 02时52分44秒
 4File Name :code/hdu/2087.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include …

hdu 1711 题目链接

题意：给定两个数列，问第二个数列在第一个数列中出现的位置（第一个元素对应的位置）

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

poj 3080 题目链接

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

poj 2185 题目链接

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

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

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

poj 2752题目链接

题意：求出所有的前缀和后缀相同的子串的长度。

思路:求出nxt函数，观察发现，从从len递归向前就是答案。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月10日 星期三 21时05分52秒
 4File Name :code/poj/2752.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring> …

hdu1686

题意：给出模式串和文本串，问模式串在文本串中出现了多少次，可以overlap.

思路：思考naive的匹配过程。nxt函数不过是改进了当失配发生时，不是移动1位，而是移动多位。nxt函数的含义是当失配发生时，移动到的位置….所以有的教程管这个叫失配函数吧，也不是很难理解的样子。

20170801update:当时竟然没有强调next函数的含义？

next[i]的含义是,i之前的整个前缀中，最长的该前缀的前缀和后缀相同的长度。

poj 2406

题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的, 求 R 的最大值

思路:论文题.

转载论文中的题解:

做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候, 先看字符串 L 的长度能否被 k 整除,**再看 suffix(1)和 suffix(k+1)的最长公共** **前缀是否等于 n-k**。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ 问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n) …