文档介绍：2017-2-1 1搜索与回溯-- junfeng_feng 2017-2-1 2 根据“信息学初学者之家”网站的统计, Ural (俄罗斯的 Ural 州立大学的简称,有名的 Ural Online Problem Set 就是该校的系统) 的题目类型大概呈如下的分布: 搜索动态规划贪心构造图论约10% 约15% 约5% 约5% 约10% 计算几何纯数学题数据结构其它约5% 约20% 约5% 约25% 统计信息: 2017-2-1 3 ——摘自《ACM 竞赛之新人向导》“算法中最基本和常用的是搜索,这里要说的是,有些初学者在学****这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言 2017-2-1 4什么是搜索算法呢? 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。 2017-2-1 5预热一下:二分查找 2 3 4 5 6 8 12 20 32 45 65 74 86 95 100 head mid tail 2017-2-1 6查找示意图: A[1]~A[15] A[1]~A[7] A[9]~A[15] A[1]~A[3] A[5]~A[7] A[1]~A[1] A[3]~A[3] …… 2017-2-1 7思考: ?1、在一百万个元素里查找某个元素大约需要比较多少次? ?2、时间复杂度: O(logN ) 2017-2-1 8举例分析从简单的字符串搜索讲起 2017-2-1 9 Sample Input 23 ABCD BCDFF BRCD 2 rose orchid Sample Output 22 HDOJ_1238 Substrings 2017-2-1 10 题目分析: ?这是一道入门级别的搜索题,基本思想比较简单,但是如果用最朴素的算法, 可能会超时如何降低算法的复杂度呢? ?下面的算法如何: ?先将字符串按长度从短到长排序,枚举最短的字符串的子串,判断是否都是别的字符串的子串,求出最大长度即可。