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位的数。 …

hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 03时22分47秒 File Name :code/hdu/3374.cpp …

hdu 4300题目链接 吐槽：题意难懂的一逼，关键的地方根本没有说清好么。。。竟然还是多校题。。。。出题人英语是体育老师教的吧。。？本来挺傻逼一道题。。被这完全没有说清楚的题意搞得很不爽。。。 题意：给一个26个字母一一对应的密码表。 然后给出一个字符串，先是密文再是明文，明文可能不全。问最小的可能的密文+明文串是什么。。 思路： 把字符串按照密码表转化得到一个新的字符串，然后跑kmp得到原字符串a的后缀等于转化后的字符串b的前缀的最长长度的字符串。（需要注意的是,kmp匹配的时候，由于密文长度一定是大于等于明文的，并且如果字符串a和字符串b相等，匹配全部是没有意义的，所以我们从中间位置开始匹配，更具体的说，是从第一个后面的字符串 …

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 …

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时12分51秒 File Name :code/hdu/2594.cpp ************************************************ */ #include …

hdu 3746题目链接 题意：给定一个字符串，是一个环（首尾相连），问至少再添加多少个珠子才能使得整个串是循环的。。。 思路：一下子想到了最小覆盖子串的模型。。。我求出最小覆盖子串的长度（n-nxt[n]）。然后特判下最小覆盖子串的长度等于字符串长度的情况。。。试着叫了一发。。。竟然就A了2333.。。大概是所谓的题感吧（逃 /* *********************************************** Author :111qqz Created Time :2016年08月12日 星期五 00时41分19秒 File Name :code/hdu/3746.cpp …

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 题意 题意：给两个字符串，将两个字符串首尾拼接之后得到一个长度最短的字符串，求这个最短的字符串（一个串的前缀可能是另一个串的后缀，这样的话只出现一次就行了） 思路：kmp。。注意和hdu 1841区分。那道题是只要得到一个串包含两个串即可。这道题是首尾拼接得到。 还要注意。。这道题要求了长度相同时按照字典序小的方法拼接。。。 /* *********************************************** Author :111qqz Created Time :2016年08月11日 星期四 05时08分32秒 File Name :code/hdu/1867.cpp …

hdu 1841题目链接 题意：给两个字符串，问包含这两个字符串的最小的字符串的长度（最小是因为，一个串的子串可能是另一个串的后缀，这样出现一次就可以了） 思路：其实这道题最关键的思想部分是和kmp没有关系的。。。 我们考虑最naive的匹配方式。 如果存在文本串的子串（之前写成了后缀，特此更正，不一定是首尾拼接，这是和hdu 1867的区别）等于模式串的前缀，那么这段子串或者后缀的长度为最后的j。 两个串各做一次模式串和文本串。 不过暴力匹配复杂度爆炸，所以用了kmp。。。 upd:代码新添加了注释。 /* *********************************************** Author :111qqz …

hdu 1358 题目链接 题意：给一个字符串，求这个字符串的每个前缀（包括本身）的能否由k个子串组成（K>1） 思路：和poj 2406 比较类似。。 结论：字符编号从0开始，如果又i%(i-next[i])==0，则i前面的 串为一个轮回串，其中轮回子串出现i/(i-next[i])次。 证明类似之前最小覆盖中的，不断的等价交换，两两相等...（这个证明在字符串这里总是遇到2333） 然而其实我。。。做的时候。。并没有想到去证明。。。而是打印出了nxt数组然后找规律求得2333. 之前一直觉得找规律不是什么拿的上台面的做法。。。但是今年打了几场多校。。尤其是电子科大的那场。。。我发现。。。其实有的题目的正解就是找规律，猜结 …