Content Preview: rss
1268 days ago
字符串匹配算法 摘要：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常 重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量，本文力图阐明字符串匹配算法的发展过程，并介绍了各个算法的特点，并给予了适当 的比较和分析。 关键字：字符串匹配 前缀 后缀 kmp算法 后缀树 Abstract: with internet booming, the amount of information gets more and more. How to find the target information in such tramendous data is the key in web searching develepment. In this end the string matching algorithm takes the key role. An efficient string matching algorithm can improve web searching service greatly. The author try to introduce the developing of the string matching algorithm and emphasis on kmp and suffix tree algorithm. Keywords: string matching suffix prefix KMP suffix tree 1.引言 查找模式字符串在文本中的所有出现是文本编辑软件经常要面对的一个问题。一般而言文本就是要编辑的文档，而模式字符串往往由用户来指定，高效的字符串匹配 算法可以提高程序的响应性能，当然字符串匹配算法的应用远远不止于此，例如在生物计算科学中查找特定的DNA序列，也是字符串匹配算法的一个重要应用。 我们可以如下定义字符串匹配问题，我们假定文本是一个长度为n的字符数组T[1..n]，而模式字符串也是一个字符数组P[1..m]，并且m <= n。进一步的，我们假定T所包含的所有字符构成一个有限的字符表E，｜E｜表示字符表所包含的自负的个数。 ...
1338 days ago
说明：递推算动归， 离散化算数据结构， 并查集算数据结构， 博弈算动归， 麻烦题一般 都是不错的综合题， 最短路算图论，数据的有序化算排序 麻烦题： 1697, 1712, 1713, 1720, 1729, 1765, 1772, 1858, 1872, 1960, 1963, 2050, 2122, 2162, 2219, 2237, 简单题目： 1000, 1003, 1004, 1005, 1007, 1046, 1207, 1226, 1401, 1504, 1552, 1607, 1657, 1658, 1674, 1799, 1862, 1906, 1922, 1929, 1931, 1969, 1976, 2000, 2005, 2017, 2027, 2070, 2101, 2105, 2109, 2116, 2136, 2160, 2190, 2232, 2234, 2275, 2301, 2350, 2363, 2389, 2393, 2413, 2419, 推荐： 1063, 1064, 1131, 1140, 1715, 2163, 杂题： 1014, 1218, 1316, 1455, 1517, 1547, 1580, 1604, 1663, 1678, 1749, 1804, 2013, 2014, 2056, 2059, 2100, 2188, 2189, 2218, 2229, 2249, 2290, 2302, 2304, 2309, 2313, 2316, 2323, 2326, 2368, 2369, 2371, 2402, 2405, 2407, 推荐： 1146, 1147, 1148, 1171, 1389, 1433, 1468, 1519, 1631, 1646, 1672, 1681, 1700, 1701, 1705, 1728, 1735, 1736, 1752, 1754, 1755, 1769, 1781, 1787, 1796, 1797, 1833, 1844, 1882, 1933, 1941, 1978, 2128, 2166, 2328, 2383, 2420, 高精度： ...
1341 days ago
poj--题目分类（转载） 1、 排序 1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 13 18, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二*排序树） 2、 搜索、回溯、遍历 1022 1111 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,208 3,2303,2310,2329 简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 17 45, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 23 49, 推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 17 14, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288 , 2331, 2339, 2340,1979（和迷宫类似） 1980（对剪枝要求较高） 3、 历法 1008 2080 （这种题要小心） 4、 枚举 1012，1046， 1387， 1411， 2245， 2326， 2363， 2381，1054（剪枝要求较高），1650 ...
1345 days ago
1.if __name__可以用来做模块测试，例如：if __name__ == __main__这样就可以判断此模块是被别的模块调用还是自己执行，如果自己执行就可以加上测试代码，而又不影响别的模块调用它，此特性非常cool。 2.字典里面的键值是唯一的，并且不可改变，它的值可以改变，只要重新指定这个键值所对应的值就可以，例如：dict['key'] = newvalue，如果要添加新的项，只要简单的执行如下语句就可dict['newkey'] = newvalue。字典中的数据注意是无序的，而且可以是任意类型的组合，也就是说并不要求一个字典里面的数据是同意类型。删除字典中的特定元素可以用 del dict['key']来实现，要想清空字典则需要调用dict.clear()方法，字典可以通过keys()方法来返回一个包括所有键值的列表。 3.python的列表支持负索引，遵循如下原则list[n] = list[n - len(list)] 一个从前向后从0开始，一个从后向前从－1开始。而且它支持分片操作也就类似字符串求字串操作，也支持负索引。列表支持两种添加操作，append在末尾 添加，insert(n,element)在索引为n处添加，原来在n的元素向后移动，类似链表操作，insert(element)与append相 同，要查找某个元素需要用list的index方法，它返回第一个匹配的元素的索引，如果不存在此元素则报异常，所以在查询某个元素的时候最好先判断此元 素是否在列表中出现，可以用in来测试，如果存在返回1，否则0。列表删除元素需要用remove方法，或pop方法，remove删除第一个匹配的元 素，如果找不到则异常，pop删除最后一个元素，并且返回它的值，很适合dfs,bfs操作。列表可以拼接就像字符串一样，它支持＋和extend两种手 段。这两种手段有些区别，+是返回一个拼接后的串，而extend则是对原来字符串的修改（类似），毕竟python的字符串是不可改变的^^，当然支持 +也就支持+=了，意义与c/c++一样，而且更进一步，它还支持*操作符，来实现相同的加法操作，例如list = ['1','2'] * 2 与list = ['1','2'] + ['1','2']相同。 ...
1350 days ago
1.phthon的html文档没有找到,如果在系统中存在的话,可以通过设置PYTHONDOCS=路径 这样就可以方便的在解释其中调用help命令,来学习phthon的命令了. 2.对于程序中存在unicode字符,需要在字符串前加u 例如:u"我用中文" ,这样才能正确处理. 3.对于正则表达式的应用python也比较方便(起码比java方便)因为,它不仅支持转义符\,还支持原语表达,在字符串前边加上r,这样就不再需要在用正则表达式的时候多写一堆的\. 4.一个字符串一旦被建立就再也不能改变,不明白好处在哪里. 5.注意python程序的每行都不要在前边加上空格,因为在python语言中缩进是有特殊意义的,缩进代表一个语句块,还有缩进尽量用统一的方法或者用TAB或者用2到4个空格,千万不要混杂,否则程序可能会出现跨平台不正确的问题. 6.python的运算符有几个特殊之处,x**y 是x的y次方,//是整除,布尔运算符是英文单词and or not,其他与c/c++ java类似. 7.python可以在函数体内声明全局变量来达到修改外部变量值的目的,关键字为global.并且支持默认参数声明,例如:haha(a = 1, b = 2);还有,当一个函数有多个参的时候,可以不用担心函数调用时参数的顺序问题,例如:haha(a,b,c) 调用时,haha(b = 2, a = 1,4)就可以,这在python中被称做关键参数. 8.python的print很强大,它支持输出次数,比如:print "hello" * 5 就会打印hello五次,默认的实现了循环的功能. 9.python中有个类似javadoc的东东,叫文档字符串,当然没有javadoc那么强大,不过也很不错拉,主要用在函数身上,函数体的逻辑第一 行的字符串就是文档字符串,然后第二行为空行,第三行开始是具体信息,整个文档字符串是在''' '''之间的.并且每行都首字符大写,以句号结束. 10.python本身是个面向对象的语言,而且非常彻底,每个函数都有自己的属性,例如上面所提到的文档字符串,就可以通过调用函数的__doc__(两个下划线连在一起)属性,来展现出来. ...
