`

字符串题目推荐及解题报告

 
阅读更多

转自:http://hi.baidu.com/fpkelejggfbfimd/item/701ab1be964e89d184dd79a6

 

POJ 1002 - 487-3279(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1002
题意:略
解法:二叉查找数,map,快排...

POJ 1200 - Crazy Search(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1200
题意:找出不相同的子串数量,字母表大小和子串长度会给定,这题很推荐hash入门者一做
解法:hash(建议karp-rabin)

POJ 1204 - Word Puzzles(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1204
题意:基本多串匹配
解法:多串匹配自动机(单串去弄肯定会超时)

POJ 1229 - Wild Domains(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1229
题意:模糊匹配
解法:dp

POJ 1625 - Censored!(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1625
题意:求长度为n不包括给定模式串的字符串数量。(题意同2778,但不能按2778的方法,建议先做此题,再做2778)
解法:Aho-Corasick自动机 + dp
相关:http://hi.baidu.com/zfy0701/blog/item/c62f41afca8180ca7cd92a19.html

POJ 1743 - Musical Theme(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1743
题意:找一个串中最长不重叠子串
解法:后缀数组+二分枚举答案,后缀数组+栈扫描,RK+二分枚举答案
相关:http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html

POJ 1816 - Wild Words(中等,绝对的Trie应用好题,同时又是搜索好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1816
题意:扩展多串模式匹配(含?, *)
解法:Trie + dfs,有兴趣也可用基于位并行的自动机(可参考柔性字符串匹配,扩展匹配章节)

POJ 2185 - Milking Grid(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2185
题意:最小矩型的覆盖
解法:KMP (不多的KMP好题)
相关:http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=33571

POJ 2513 - Colored Sticks(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2513
题意:转化成欧拉回路
解法:并查集+hash,并查集+Trie

POJ 2774 - Long Long Message(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2774
题意:找两个串的公共最长子串
解法:后缀数组,Oracle Factor自动机,后缀自动机
相关:http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
http://hi.baidu.com/zfy0701/blog/item/d9fedbd14581113d9b5027ab.html

POJ 2778 - DNA Sequence(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2778
题意:求长度为n不包括给定模式串的字符串数量。
解法:Aho-Corasick自动机(前缀树) + 矩阵快速乘法
相关:http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
类似于1625,建议先做1625

POJ 1699 - Best Sequence(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1699
题意:转换为TSP问题(注意子串的包含关系!)
解法:回溯,状态dp

POJ 3376 - Finding Palindromes(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3376
题意:找回文串组合
解法:找出规律,然后Trie + kmp推广形式

POJ 3415 - Common Substrings(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3415
题意:统计两个串中长度>=k的公共子串的数量
解法:后缀数组+栈扫描,后缀自动机
相关:http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html

POJ 3080 - Blue Jeans(如果用暴力,就很简单)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3080
题意:求n个串的最长公共子串
解法:后缀数组+栈扫描,后缀数组+二分枚举,暴力
相关:http://hi.baidu.com/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html

POJ 3208 - Apocalypse Someday(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3208
题意:略
解法:有意思的自动机dp

POJ 3261 - Milk Patterns(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3261
题意:求一个串中重复出现至少k次的最长子串
解法:后缀数组+栈扫描,hash + 二分

POJ 3294 - Life Forms(较难,强烈推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3294
题意:n个串中,为大于n/2个串所共有的所有最长子串
解法:后缀数组+栈扫描,暴力(很容易被卡掉),后缀数组+线段树(?)
相关:http://hi.baidu.com/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html

POJ 3576 - Language Recognition(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3576
题意:求一个dfa,它满足两个条件,1、能识别所有词的dfa,2、要求状态数最少。
解法:trie + hash
相关:http://hi.baidu.com/zfy0701/blog/item/b8332b5cd90e7b45fbf2c033.html

POJ 3581 - Sequence(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3581
题意:把原串分三段并反转,求字典序最小的那串
解法:后缀数组
本来觉得很水,但却是我目前做得最失败的一道后缀数组题

 

POJ 3630 - Phone List(基础,强烈推荐用此题练Trie)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3630
题意:给n个串,看是否有一个串是另一个串的前缀
解法:快排,Trie

POJ 3690 - Constellations(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3690
题意:二维串匹配
解法:转换为一维,或者用多串匹配

POJ 3691 - DNA repair(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3691
题意:修复非法字符串需要替换的最少字符数
解法:动态规划,如果使用AC自动机去做dp的话比较简单且只需要二维,用dp[i][j]表示第i个字符时,第j种状态(不是非法状态)所需要最小的修改量

POJ 3693 - Maximum repetition substring(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3693
题意:求最循环节最多的子串
解法:我所知道的最好的做法应该是先做s-factorization(也就是lempel-ziv),然后在分解之后的每一段中枚举周期,周期可以通过推导关系式确定是否合法,然后可确定循环次数,取最大的,中间还用到了对kmp的扩展。具体来说有KK算法,和ML算法两种,其中ML不能遍历所有的runs。

其他OJ:

SPOJ 2743 - Prefix Tiling
http://www.spoj.pl/problems/PRETILE/

找规律

空罐 Cans(这个自动机dp还是有意思的)
http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=b179

HDOJ 2471 - History of Languages(杭州现场赛)
http://acm.hdu.edu.cn/showproblem.php?pid=2471
自动机的等价性,划分集合的dp

HDU 2967 - Morphing is fun
http://acm.hdu.edu.cn/showproblem.php?pid=2967
UVA上也过得人比较少的一道题,需要分情况讨论几种情况,我09年过的最得意的题

 

欢迎关注微信公众号——计算机视觉:

 

 

分享到:
评论

相关推荐

    python编程题:字符串的(所有可能的)排列组合.docx

    题目内容 在指定位置编写代码,完成函数,根据给定的字符串,给出组成该字符串的字符的所有排列构成的字符串,例如字符串为abc时,结果为abc、acb、bac、bca、cab、cba。(提示:可以考虑拿掉某个位置的字符,则"该...

    LeetCode 面试题 01.06. 字符串压缩

    字符串压缩题目解题思路图解代码实现实现结果补充 面试题 01.06. 字符串压缩 题目来源:https://leetcode-cn.com/problems/compress-string-lcci 题目 字符串压缩。利用字符重复出现的次数,编写一种方法,实现...

    Andy619-Zhu#CS-Notes-chu#48. 最长不含重复字符的子字符串1

    48. 最长不含重复字符的子字符串题目描述输入一个字符串(只包含 a\~z 的字符),求其最长不含重复字符的子字符串的长度。解题思路int preI = pre

    剑指Offer(Python多种思路实现):最长不含重复字符的子字符串

    题目:最长不含重复字符的子字符串 题:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长字符串的长度。假设字符串中只包含‘a’-‘z’的字符。例如,在字符串“arabcacfr”中,最长的不含重复字符...

    算法修炼之路—【字符串】Leetcode 345 反转字符串中的元音字母

    编写一个函数,以字符串作为输入,反转该字符串中的元音字母。 示例1: 输入: s = “hello” 输出: “holle” 示例2: 输入: s = “leetcode” 输出: “leotcede” 思路分析 难度是简单 ,我们首先要明确元音...

    3级数据库上机100题.doc

    【解题思路】首先用字符串函数strlen求出字符串s的长度,赋给变量strl;再把字符串的首字符赋给字符变量ch;然后在for循环语句中,变量i从0递增到strl-1,字符串s中的所有字符左移一个位置;最后把字符变量ch的值赋...

    北大1147解题报告

    是经过一个由0和1组成的字符串经过左移形成的共n个串再经过由小到大排序而组成的矩阵,如 00011->00110->01100->11000->10001,得到了5个串,此5个串由小到到排序(2进制数排序)为00011 00110 01100 10001 11000,...

    剑指Offer(Python多种思路实现):表示数值的字符串

    题目:表示数值的字符串 题:请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100″,”5e2″,”-123″,”3.1416″和”-1E-16″都表示数值。 但是”12e”,”1a3.14″,”1.2.3″,”+-5″...

    python实现将字符串中的数字提取出来然后求和

    题目:字符串43…3y2.f67se2.666. 将其中的所有数字提取出来然后求和 思考: 1、字符串中包含了字母和数字和小数点,怎么取出来比较呢? 2、小数点连续有很多个的时候怎么处理? 3、最后取出来的数该怎么求和? 4、...

    LeetCode 最长回文串

    文章目录最长回文串题目解题思路代码实现实现结果 最长回文串 题目来源:https://leetcode-cn.com/problems/longest-palindrome/ 题目 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的...

    dzw001#leetcode_notebook#459.重复的子字符串1

    题目链接题目描述题目难度:简单给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。解题思路遍历 s 的所有前缀,首先检查该前缀的长度是否能将

    python中字符串变二维数组的实例讲解

    在用python定义一个二维数组时可以有list和numpy.array两种方式,看了几篇python中二维数组的建立的博客发现大多都是建立的初始化的二维数组,而我需要通过文件读取得到的是字符串,再把字符串转换为二维数组,找不...

    数据结构与算法Python版——第四周作业

    1有序队列(10分) ...分析:题目规定 “每次移动中,选择最左侧的字母,将其从原位置移除,并加到字符串的末尾”,这样的操作可以让人联想到 队列的属性:FIFO。 解题思路: 1.先定义队列的类(注意

    算法修炼之路—【字符串】Leetcode 521 最长特殊序列I

    文章目录题目描述思路分析解题代码复杂度分析Github源码 题目描述 给你两个字符串,请你从这两个字符串中找出最长的特殊序列。 最长特殊序列 定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子...

    翻转字符串

    文章目录翻转字符串翻转字符串单词顺序算法思路相应代码字符串整体移动算法思路相应代码 翻转字符串 翻转字符串单词顺序 【题目】 给定一个字符类型的数组chas,请在单词间做逆序调整。只要做到单词顺序逆序即可,对...

    AlgorithmAndLeetCode#itcharge-LeetCode-Py#1446. 连续字符1

    1446. 连续字符标签:字符串难度:简单题目大意给你一个字符串 s ,字符串的「能量」定义为:只包含一种字符的最长非空子字符串的长度。解题思路使用 count

    剑指Offer(Python多种思路实现):把数字翻译成字符串

    题目:把数字翻译成字符串 题:给定一个数字,我们按照如下规则把它翻译为字符串:0翻译成“a”,1翻译成“b”,……,11翻译成“1”,……,25翻译成“z”。一个数字可能有多个翻译。例如:12258有5种不同的翻译,...

    手动汇总python的基础练习题

    python学习过程中题目很多,特写此记录部分习题,解题方法不一定最佳,欢迎文末讨论。 索引python基础习题T1 字符串密码强度T2 复制文档并添加行号T3 MD5T4 excel操作总结 T1 字符串密码强度 题干: “一般作为密码...

    最大公共字符串leetcode-leetcode:坚持每周刷一道LeetCode题

    最大公共字符串leetcode leetcode刷题打卡 接下来,坚持每周至少刷一道LeetCode题,刷题顺利按照牛客网LeetCode经典题目顺序进行,记录解题思路,与大家共享,同时也做个自我监督 第一周 1、树 题目: Given a ...

Global site tag (gtag.js) - Google Analytics