`

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

阅读更多

转自: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年过的最得意的题

 

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

 

 

分享到:
评论

相关推荐

    pku hdu zoj题目分类

    "poj pku字符串题目推荐及解题报告.doc"专注于字符串处理,这是编程竞赛中常见的一类问题,包括模式匹配、KMP算法、Manacher's Algorithm等。 7. **ACM应掌握的知识点**: "ACM应掌握的知识点.doc"可能是对参加...

    C语言字符串练习(习题+答案).zip

    在资源中的"C语言练习--字符串篇.docx"文档中,可能包含以下几种类型的字符串题目: 1. 字符串初始化与复制:了解如何初始化字符串,以及如何使用strcpy()函数进行字符串复制,避免缓冲区溢出的问题。 2. 字符串...

    字符串面试题整理

    以下是一些与字符串相关的面试题目及其解题思路: 1. **字符串循环左移**:给定一个字符串和一个整数k,将字符串中的每个字符向左移动k个位置。例如,字符串"abcdefg",k=2,移动后的结果为"efgabcd"。可以使用双...

    北大acm经典题目解题报告

    【北大ACM经典题目解题报告】是一份深入解析北京大学ACM竞赛训练中经典问题的文档,旨在为那些准备参加ACM(国际大学生程序设计竞赛)的同学们提供宝贵的参考资料。这份报告不仅涵盖了丰富的算法知识,还揭示了面对...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    字符串处理算法

    在当今的计算机科学领域,字符串处理是一个极其重要的课题,尤其在算法竞赛如ACM(ACM国际大学生程序设计竞赛)中,高效的字符串处理算法是解决许多问题的关键。本文将介绍一些常见的字符串处理算法:Hash、KMP、...

    OJ_字符串加解密

    4. **字符串处理函数**:C语言中的`strlen()`用于获取字符串长度,`strcpy()`和`strncpy()`用于复制字符串,`strcat()`和`strncat()`用于连接字符串,`strchr()`和`strstr()`用于查找子字符串,这些函数可以辅助我们...

    统计字符串中数字、字母和空格的个数

    本题目旨在通过一个简单的例子介绍如何统计字符串中的不同字符类型(数字、字母和空格)的数量。这对于初学者来说是一个很好的练习项目,可以帮助他们更好地理解字符编码、条件判断以及循环等基本概念。 #### 题目...

    Codeforces题目泛做解题报告许昊然.pdf

    **解题思路**:回文字符串是指正反读都一样的字符串。这类问题通常可以通过动态规划或者Manacher算法来解决。动态规划方法的核心思想是构建一个二维数组来记录每个子串是否为回文串,而Manacher算法则可以直接求出...

    杭州电子科技大学OJ解题报告

    【杭州电子科技大学OJ解题报告】涉及到的是在线编程竞赛(Online Judge,简称OJ)中的算法题目解题过程。OJ系统允许参赛者提交代码并自动运行测试,以检验程序是否能正确解决特定问题。这里提到的解题报告可能包括了...

    2009ACM校赛题目及输入输出解题报告

    题目难度各异,涉及图论、动态规划、数学、字符串处理、搜索算法等多种计算机科学领域的知识。 2009年ACM校赛的题目文件可能包括问题描述、样例输入和输出,以及可能的限制条件。这些问题要求参赛者不仅要有扎实的...

    北大poj解题报告

    6. **问题分类与解题策略**:POJ题目涵盖了各种类型,如数学问题、字符串处理、图形问题等。解题报告会根据问题类型提供相应的解题策略,帮助读者形成解决问题的思维框架。 7. **实际应用与扩展**:除了POJ平台上的...

    poj 经典题目解题报告

    《POJ经典题目解题报告》是一份针对北京大学ACM题库系统的解题总结,主要针对C语言编程爱好者和竞赛选手。ACM,全称国际大学生程序设计竞赛(International Collegiate Programming Contest),是一项全球性的编程...

    亲密字符串判断1

    题目“亲密字符串判断1”属于字符串处理的范畴,主要考察对字符串的比较、遍历以及字符计数的理解。这个问题要求我们判断两个给定的字符串 A 和 B 是否能通过交换其中的两个字符变成相等的字符串。 首先,我们需要...

    最长字符串1

    在这个题目中,我们面对的是一个简单的算法问题,目标是找出给定的5个字符串中的最长字符串。这属于字符串处理和算法设计的范畴,通常在编程竞赛或者算法训练中出现。解决此类问题,我们可以采用多种方法,包括但不...

    北大ACM经典题目解题报告

    【北大ACM经典题目解题报告】是一份深入解析北京大学在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)赛事中所遇到的经典问题的资料。这份报告旨在帮助参赛者理解和解决这类竞赛中...

    字符数组与字符串 资料集(2024.06.08).pdf

    - 例如:“入门 5”字符串题目可以帮助理解基本的字符串操作。 2. **OpenJudge NOI 题库**: - 包含了大量的编程基础之字符串题目,涵盖各种难度。 - 适合进一步提高解题技巧和应对竞赛级别的挑战。 ### 五、...

    安徽省第六届安徽省大学生程序设计竞赛题目和解题报告

    3. 字符串处理:可能涉及到模式匹配、字符串搜索和编辑距离计算等。 4. 数据结构:可能需要使用栈、队列、树、图、哈希表等数据结构。 5. 动态规划:一些复杂的题目可能需要使用动态规划来求解最优化问题。 通过...

    IOI2014解题报告

    题目可能涉及到图论、动态规划、字符串处理、数值计算、几何算法等多个领域。 3. 评分标准:选手提交的程序会被自动测试系统按照输入数据进行测试,程序必须在规定的时间和空间限制下正确处理所有测试数据才算通过...

Global site tag (gtag.js) - Google Analytics