字符串匹配算法
摘要：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常 重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量，本文力图阐明字符串匹配算法的发展过程，并介绍了各个算法的特点，并给予了适当 的比较和分析。
关键字：字符串匹配 前缀 后缀 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｜表示字符表所包含的自负的个数。
本文所提及的字符串匹配算法除了朴素字符串匹配算法以外都需要一定的预处理时间，此预处理时间根据算法的不同也不尽相同，图1展示了本文将要提到的各个算 法所需要的预处理时间以及匹配的时间，可以大致看出字符串匹配算法的演变过程，而且会发现后缀树算法与其他算法有很大的不同，而正是由于这一点使得后缀树 的应用更加贴近于今天互联网的大环境。
2.朴素字符串匹配算法
朴素字符串匹配算法的思想非常直白，既然是查找模式字符串在文本字符串中的出现，那么我么就从文本字符串的每一位开始一次判断是否与模式字符串相同，如果 相同那么就找到了模式字符串的一次出现，可以看出此算法的时间复杂度为O(mn)，m,n分别为文本字符串与模式字符串的长度，但是通过更加深入的分析可 以得出此算法的平均时间复杂度为O（n+m），所以此算法在模式字符串与文本字符串都是随即选择的情况下工作地是相当的不错，还有就是此算法并没有其他算 法所必须的预处理时间。
3.Rabin-Karp算法
Rabin-Karp算法是由Rabin和Karp[1]提出的一个在实际中有比较好应用的字符串匹配算法，此算法的预处理时间为O(m)，但它的在最坏 情况下的时间复杂度为O((2n-m+1)m)，而平均复杂度接近O(m+n)，此算法的主要思想就是通过对字符串进行哈稀运算，使得算法可以容易的派出 大量的不相同的字符串，假设模式字符串的长度为m，利用
Horner法则p = p[m] + 10(p[m -1] + 10(p[m-2]+...+10(p[2]+10p[1])...))，求出模式字符串的哈稀值p,而对于文本字符串来说，对应于每个长度为m的子串的 哈稀值为t(s+1)=10(t(s)-10^(m-1)T[s+1])+T[s+m+1]，然后比较此哈稀值与模式字符串的哈稀值是否相等，若不相同， 则字符串一定不同，若相同，则需要进一步的按位比较，所以它的最坏情况下的时间复杂度为O（mn）。
4.字符串匹配自动机
与字符串相关的自动机[2]是一个五元组（Q，q,A,E,%）其中Q是状态的有限集合，q<Q是开始状态，A<+Q是接受状态的集合，E是 输入字符集合，%是一个QXE->Q的映射，称为转移函数。通过模式字符串，我们可以构造出识别此字符串的自动机，此自动机对应于字符表中的任何一 个输入在某个状态下都有一个转移到另一个状态（包括它自身），当进行到接受状态时就找到了模式字符串在目标字符串中的一次出现，由于自动机需要对于任何一 个字符集中出现的字符都给出相应的转移，也就意味着构造自动机的时间复杂度与|E|有关，而事实上，构造自动机的时间复杂度为O（m^3|E|）,但当此 自动机构造完成后，搜索目标字符串的时间为O(n)。
5.KMP算法
现在要提到一个伟大的算法，它的出现归功于Knuth,Morris和Pratt的伟大工作[3],此算法采用类似上面所提到的字符串自动机的原理，但完 全避免了计算转移函数，它仅仅用了一个只需要O(m)就能计算出来的辅助函数pai[1..m]就达到了搜索时间复杂度为O(n).
函数pai称为前缀函数，是根据模式字符串构造的，对于一个给定的模式字符串p[1..m]，它的前缀函数定义如下：pai[q] = max{k:k<q and p(k) > p(q)}即：pai[q]是p的最长的与后缀p(q)相同的前缀。
通过均摊分析可以证明计算前缀函数的时间复杂度为O(m),而同样把此方法用于分析KMP算法的时间复杂度分析，我们可以得出KMP匹配算法的时间复杂度为O(m+n)。
6.后缀树算法
6－1后缀字典树算法
对于目标字符串的所有后缀，可以把他们构造成字典树，此字典树的每一个节点（除叶子节点外）,都可能有｜E｜个分支，这样在目标字符串中搜索模式字符串的 出现变得非常的简单，只需要从字典树的跟节点出发，按照对应的分支向下查找，最多比较m次，就可以确定此模式字符串是否在目标字符串钟出现。所以查找字符 串的时间复杂度为O(m)与目标字符串n无关，这种好处是非常明现的，它意味着对于一个目标字符串一旦建立它的后缀字典树后，以后在此目标字符串查找任意 字符串都只需要O(m)的比较，但是构造后缀字典树无疑是很花费时间与空间的，通过分析可以知道，构造此字典树的时空花费为O（n^2），对于很大的目标 字符串来说，这是无法忍受的。
6-2非在线后缀树算法
为了减少构造后缀字典树所花费的时间与空间，Edward McGreight[4] 1976年发表了后缀树的论文，此后缀树与后缀字典树在代表的含义上完全相同，但由于它采用了路径压缩的方法，即每条边不只代表一个字符，有可能是一个字 符串，大大节省了构造此后缀树所花的时间与空间，可以证明此后缀树最多有2n个节点，构造的时间为O(n)，但是此算法有个非常明显的缺点，就是它的倒序 处理字符串的，也就是它是非在线的。
6－3在线后缀树算法
1995年Ukkonen[5]提出了在线的后缀树算法，支持从左到右的输入字符串，并在输入的同时构造出后缀树，至此给后缀树画上了完美的句号，通过分析可以知道基于后缀树的字符串匹配算法的时间复杂度为O(m+n)。
7.总结
通过上面的阐述，我们可以清出的看出一个问题的提出经常半随着一个新算法的出现，而一个新算法的出现又会带来一些新的问题。前面所述的这些算法虽然从理论 上来说一个比一个高效，但是在实际应用中，每个算法都有自己独特的价值，即便是最原始的朴素字符串匹配算法也仍然有较好的应用，因为它的平均性能很好，而 且不需要预处理时间。而Rabin-Karp算法则往往用于单个模式字符串在多个目标字符串中的同时查找，以及模糊匹配。KMP无疑是应用最广的而且它的 实现也很简单，几乎无所不在。后缀树算法对于在同一个目标文本中查找多个模式字符串则非常的适合，尤其对于很大的目标文本，工作地非常好，所以在网络搜索 中成为了主流算法。目前后缀树的研究已经比较成熟，主要在进行后缀数组的研究，后缀数组与后缀树的想法相同，但是在实现上更加高效，不过它并不是O(n) 的算法，但是由于其简单的结构，高效的实现使得它的应用非常的诱人。字符串匹配算法还有很多，这里只是提到一些比较经典的算法，不过沿着字符串匹配算法的 轨迹，我们可以清楚的看到它的迷人之处。
Reference
[1]Richard M.Karp and Michael O.Rabin. Efficient randomized pattern-matching algorithms. Technical Report Tr-31-81,aiken Computation Laboratory.Harward University,1981.
[2]Alfred V.Aho,John E.Hopcroft,and Jeffrey D.Ullman. The Design and Analysis of Computer Algorithms.Addison-Wesley,1974.
[3]Donarld E.Knuth. Big omnicron and big omega and big theta.ACM SIGACT News, 8(2). 18-23,1976.
[4]E.M.Mclreight. A Space-Economical Suffix Tree Construction Algorithm. Jrul of Algorithms,23(2) pp262-272,1976.
[5]E.Ukkonen. On-line Construction of Suffix Trees. Algorithmica,14(3)pp249-260,1995.
[6]Mark Nelson.Fast String Searching with Suffix Trees.Dr. Dobb's Journal August,1996.
[7]P.Weiner. Linear Pattern Matching Algorithms.Proc.14th IEEE Annual Symp on Switching and Automata Theory,pp1-11,1973.
[8]D.E.Knuth,J.H.Morris and V.R.Pratt. Fast Pattern Matching in Strings. SIAM Jrul Comput,6(2) p323-350 Jun,1997.
[9]G.de V.Smit. A comparision of Three String Matching Algorithms.Software Practice and Experience 12 p57-66 Jan, 1982.
[10]T.H.Cormen,C.E.Leiserson,R.L.Rivest and C.Stein. Introduction to Algorithms(2nd edition). The MIT Press.
[11]http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix
[12]http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Strings
[13]http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm

说明：递推算动归， 离散化算数据结构， 并查集算数据结构， 博弈算动归， 麻烦题一般
都是不错的综合题， 最短路算图论，数据的有序化算排序

麻烦题：
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,

高精度：
1001, 1220, 1405, 1503,

排序：
1002, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 2388, 2418,
推荐：
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,

搜索
容易：
1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745,
1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,
不易：
1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349,
推荐：
1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714,
1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288,
2331, 2339, 2340,

数据结构
容易：
1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395,
不易：
1145, 1177, 1195, 1227, 1661, 1834,
推荐：
1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119,
2274,

动态规划
容易：
1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276,
1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926,
1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029, 2033, 2063, 2081,
2082, 2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385,
2392, 2424,
不易：
1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707, 1733, 1737,
1837, 1850, 1920, 1934, 1937, 1964, 2039, 2138, 2151, 2161, 2178,
推荐：
1015, 1635, 1636, 1671, 1682, 1692, 1704, 1717, 1722, 1726, 1732, 1770, 1821,
1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411,

字符串：
1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896,
1951, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408,

贪心：
1042, 1065, 1230, 1323, 1477, 1716, 1784,

图论
容易：
1161, 1164, 1258, 1175, 1308, 1364, 1776, 1789, 1861, 1939, 1940, 1943, 2075,
2139, 2387, 2394, 2421,
不易：
1041, 1062, 1158, 1172, 1201, 1275, 1718, 1734, 1751, 1904, 1932, 2173, 2175,
2296,
网络流：
1087, 1273, 1698, 1815, 2195,
匹配：
1274, 1422, 1469, 1719, 2060, 2239,
Euler：
1237, 1637, 1394, 2230,
推荐：
2049, 2186,

计算几何
容易：
1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318,
不易：
1685, 1687, 1696, 1873, 1901, 2172, 2333,
凸包：
1113, 1228, 1794, 2007, 2187,

模拟
容易：
1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791,
1835, 1970, 2317, 2325, 2390,
不易：
1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,

数学
容易：
1061, 1091, 1142, 1289, 1305, 1306, 1320, 1565, 1665, 1666, 1730, 1894, 1914,
2006, 2042, 2142, 2158, 2174, 2262, 2305, 2321, 2348,
不易：
1067, 1183, 1430, 1759, 1868, 1942, 2167, 2171, 2327,
推荐：
1423, 1450, 1640, 1702, 1710, 1721, 1761, 1830, 1930, 2140,

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
（小数的精度问题）

5、   数据结构的典型算法

容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395,
不易：1145, 1177, 1195, 1227, 1661, 1834,
推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 21
19, 2274, 1125(弗洛伊德算法) ，2421（图的最小生成树）

6、 动态规划

1037 A decorative fence、
1050 To the Max、
1088 滑雪、
1125 Stockbroker Grapevine、
1141 Brackets Sequence、
1159 Palindrome、
1160 Post Office、
1163 The Triangle、
1458 Common Subsequence、
1579 Function Run Fun、
1887 Testing the CATCHER、
1953 World Cup Noise、
2386 Lake Counting

7、 贪心

1042, 1065, 1230, 1784,1328 1755（或用单纯形方法），2054，101
7， 1328，1862， 1922 ，2054， 2209， 2313， 2325， 2370。

8、 模拟

容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 17
91, 1835, 1970, 2317, 2325, 2390,
不易：1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,1281 1928 2083 2141 2015

9、   递归

1664

10、字符串处理

1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 19
51, 2003, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408, 1016 1051 1126 1
318 1572 1917 1936 2039 2083 2136 2271 2317 2330，2121 2403

11、数论

1006,1014,1023,1061,1152,1183,1730,2262

12、几何有关的题目

凸包：1113, 1228, 1794, 2007, 2187,1113 wall，2187 beauty contest
容易：1319, 1654, 1673, 1675, 1836, 2074, 2137, 2318,
不易：1685, 1687, 1696, 1873, 1901, 2172, 2333,

13、任意精度运算、数字游戏、高精度计算

1001 1023 1047 1060 1079 1131 1140 1142 1207 1220 1284 1289 1306 1316 1338 1405
1454 1503 1504 1519 1565 1650 1969 2000 2006 2081 2247 2262 2305 2316 2389
1001, 1220, 1405, 1503,1001（高精度乘法） 2413(高精度加法，还有二分查找)

14、概率统计

1037,1050

15、小费用最大流、最大流

2195 going home，2400 supervisor, supervisee，1087 a plug for UNIX，1149 PIGS，1
273 drainage ditches，1274 the perfect stall，1325 machine schedule，1459 power
network，2239 selecting courses

16、压缩存储的DP

1038 bugs integrated inc，1185 炮兵阵地，2430 lazy cow

17、最长公共子串（LCS）

1080 human gene functions，1159 palindrome，1458 common subsequence，2192 zipper

18、图论及组合数学

2421 Constructing Roads、
2369 Permutations、
2234 Matches Game、
2243 Knight Moves、
2249 Binomial Showdown、
2255 Tree Recovery、
2084 Game of Connections、
1906 Three powers、
1833 排列、
1850 Code、
1562 Oil Deposits、
1496 Word Index、
1306 Combinations、
1125 Stockbroker Grapevine、
1129 Channel Allocation、
1146 ID Codes、
1095 Trees Made to Order、找规律
2247 Humble Numbers、
2309 BST、
2346 Lucky tickets、
2370 Democracy in danger、
2365 Rope、
2101 Honey and Milk Land
2028 When Can We Meet?、
2084 Game of Connections、
1915 Knight Moves、
1922 Ride to School、
1941 The Sierpinski Fractal、
1953 World Cup Noise、
1958 Strange Towers of Hanoi、
1969 Count on Canton、
1806 Manhattan 2025、
1809 Regetni、
1844 Sum、
1870 Bee Breeding、
1702 Eva\'s Balance、
1728 A flea on a chessboard、
1604 Just the Facts、
1642 Stacking Cubes、
1656 Counting Black、
1657 Distance on Chessboard、
1662 CoIns、
1663 Number Steps、
1313 Booklet Printing、
1316 Self Numbers、
1320 Street Numbers、
1323 Game Prediction、
1338 Ugly Numbers、
1244 Slots of Fun、
1250 Tanning Salon、
1102 LC-Display、
1147 Binary codes、
1013 Counterfeit Dollar、

19、博弈类

1067 取石子游戏、
1740 A New Stone Game、
2234 Matches Game、
1082 Calendar Game 、
2348 Euclid\'s Game、
2413 How many Fibs?、
2419 Forest

20、简单、模拟题
1001 Exponentiation 、
1002 487-3279、
1003 Hangover 、
1701 Dissatisfying Lift、
2301 Beat the Spread!、
2304 Combination Lock、
2328 Guessing Game、
2403 Hay Points 、
2406 Power Strings、
2339 Rock, Scissors, Paper、
2350 Above Average、
2218 Does This Make Me Look Fat?、
2260 Error Correction、
2262 Goldbach\'s Conjecture、
2272 Bullseye、
2136 Vertical Histogram、
2174 Decoding Task、
2183 Bovine Math Geniuses、
2000 Gold Coins、
2014 Flow Layout、
2051 Argus、
2081 Calendar、
1918 Ranking List、
1922 Ride to School、
1970 The Game、
1972 Dice Stacking、
1974 The Happy Worm、
1978 Hanafuda Shuffle、
1979 Red and Black、
1617 Crypto Columns、
1666 Candy Sharing Game、
1674 Sorting by Swapping、
1503 Integer Inquiry、
1504 Adding Reversed Numbers、
1528 Perfection、
1546 Basically Speaking、
1547 Clay Bully、
1573 Robot Motion、
1575 Easier Done Than Said?、
1581 A Contesting Decision、
1590 Palindromes、
1454 Factorial Frequencies、
1363 Rails、
1218 THE DRUNK JAILER、
1281 MANAGER、
1132 Border、
1028 Web Navigation、

21、初等数学

1003 Hangover、
1045 Bode Plot、
1254 Hansel and Grethel、
1269 Intersecting Lines、
1401 Factorial、
1410 Intersection、
2363 Blocks 、
2365 Rope、
2242 The Circumference of the Circle、
2291 Rotten Ropes、
2295 A DP Problem、
2126 Factoring a Polynomial、
2191 Mersenne Composite Numbers、
2196 Specialized Four-Digit Numbers、
1914 Cramer\'s Rule、
1835 宇航员、
1799 Yeehaa!、
1607 Deck、
1244 Slots of Fun、
1269 Intersecting Lines、
1299 Polar Explorer、
1183 反正切函数的应用、

22、匹配

1274, 1422, 1469, 1719, 2060, 2239

===================================

经典
1011（搜索好题）
1012（学会打表）
1013
1019（它体现了很多此类问题的特点）
1050（绝对经典的dp）
1088（dp好题）
1157（花店，经典的dp）
1163（怎么经典的dp那么多呀？？？）
1328（贪心）
1458（最长公共子序列）
1647（很好的真题，考临场分析准确和下手迅速）
1654（学会多边形面积的三角形求法）
1655（一类无根树的dp问题）
1804（逆序对）
2084（经典组合数学问题）
2187（用凸包求最远点对，求出凸包后应该有O(N)的求法，可我就是调不出来）
2195（二分图的最佳匹配）
2242（计算几何经典）
2295（等式处理）
2353（dp，但要记录最佳路径）
2354（立体解析几何）
2362（搜索好题）
2410（读懂题是关键）
2411（经典dp）



趣味
1067（很难的数学，但仔细研究，是一片广阔的领域）
1147（有O(n)的算法，需要思考）
1240（直到一棵树的先序和后序遍历，那么有几种中序遍历呢？dp）
1426（是数论吗？错，是图论！）
1648（别用计算几何，用整点这个特点绕过精度的障碍吧）
1833（找规律）
1844（貌似dp或是搜索，其实是道有趣的数学题）
1922（贪心，哈哈）
2231
2305（不需要高精度噢）
2328（要仔细噢）
2356（数论知识）
2359（约瑟夫问题变种）
2392（有趣的问题）



很繁的题
1001
1008
1087（构图很烦，还有二分图的最大匹配）
1128（USACO）
1245
1329
1550（考的是读题和理解能力）
1649（dp）
2200（字符串处理+枚举）
2358（枚举和避免重复都很烦）
2361（仔细仔细再仔细）



难题

1014（数学证明比较难，但有那种想法更重要）
1037（比较难的dp）
1405（高精度算法也分有等级之分，不断改进吧）
2002（不知道有没有比O(n^2*logn)更有的算法？）
2054（极难，很强的思考能力）
2085（组合数学）
2414（dp，但要剪枝）
2415（搜索）
2423（计算几何+统计）



多解题
1002（可以用排序，也可以用统计的方法）
1338（搜索和dp都可以）
1664（搜索和dp都练一练吧）
2082（这可是我讲的题噢）
2352（桶排和二*树都行）



Note:
1011: 很经典的剪支
1014: 难在数学上
1017: 严格的数学证明貌似不容易
1021: 有点繁,考察对图形进行各种旋转的处理
1083: 巧妙的思考角度
1150: 分奇偶讨论,lg(n)算法
1218: 三行就够了,虽然简单,但也有优劣之别
1505: 二分加贪心
1654: 做法也许很多吧,本人用有向面积做的
1674: 计算圈的个数(算是graph 吧)
1700: 数学证明不容易
1742: O(m*n)的算法
1863: 要耐心地慢慢写…^_^
1988: 并查集
2051: 堆
2078: 不难，但剪支可以做到很好
2082::O(n),你想到了吗？
2084: 卡特兰数
2182: 线段树
2195: 最小费用最大流
2234: 经典博弈算法
2236: 并查集
2299: 二分思想
2395: Kruskal 最小生成树的拓展
2406: KMP
2411: 用二进制串来表示状态

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']相同。
3.元组与列表类似，但是它是不可改变的，所以不支持删除，添加，拼接等操作，而且比较奇怪的是它也不支持index操作，但是支持in关键字来判断是否 存在某个元素，它可以通过list方法来转变成一个列表，列表也可以通过tuple函数转换成员组，它的好处在于，比列表的操作要快（想想， linkedlist和arraylist),还有它也可以作为字典的键值，列表不可以，还有可以格式化输出。元组还有一点需要注意，就是声明空元组用 （），一个元素的元组需要用（element,）与表达式相区分。
4.python语言的变量也分为局部变量还有全局变量，也有作用域的概念，而且不需要声明，变量通过赋值来产生，超出作用域后自动湮灭。与java一 样，一个变量没有初始化，在这里就是没有赋值，编译会报错，这能避免多少错误！引用一句话：“早晚有一天你会为此而感谢Python。”
5.python的格式化输入输出与c非常相像，但只支持%s%d。
6.列表映射非常有用，它通过循环遍历列表中的每一个元素，通过一个固定的函数来改变元素的值形成一个新的列表，但并不改变原有的列表。
7.python的字符串有一个非常有用的方法join,string.join(list)可以将列表list的每一个元素用string分隔开后链接 成一个新的字符串，与此对应的是字符串的split方法，此方法与java中的字符串的split方法一样，只不过功能要小一些。split当不带任何参数的时候默认按照空格分割。
8.from ... import ....用法有一点比较方便，引入的方法或变量可以当成局部变量来使用，不需要通过模块名来限定。如果你要经常使用引入模块的方法或变量，那么用此语法， 又或者你想只用引入模块的某些方法和变量，那么也应该用此语法，当如果你的模块中有方法或变量与引入的模块的变量或方法重名，那么应该用import ...语法，避免名称冲突。
9.python有几个非常有用的内置函数，他们都属于一个叫做__builtsin__的模块，可以认为，每个python程序都默认的在开始的时候导 入此模块，这样就可以在python中自有的使用这些内置函数，如：type,str,dir;type是返回任何对象的类型（对象意味着python中 的一切），str是返回任何对象的字符串形式，dir是返回任何对象的所有属性和方法。
10.getattr()是个十分有用的函数，他返回的是一个方法或者函数的引用有点类似cin,cout一样，例如：getattr(list, 'pop')返回的是list.pop()的引用，而getattr(list,'pop')('element') = list.pop('element')。而且他不仅适用内置的数据类型，还适用于模块。
11.python中有一个类似c中的?:的语法结构，就是and or : bool and a or b当bool = True 输出a, bool = False输出b,但是也不是总成立，当a = false的时候就与?:表现不一致，因为and or完全是一个逻辑表达式，并不特殊，当然可以采取一些手段来达到与?:一样，可以把它封装到list中，这样a就永远不可能为假，最好做成一个函数 def choose(bool,a,b): return (bool and [a] or [b])[0]。
12.lambda函数实际上是一个内联函数，好处就不用多说，它只支持一行的表达式返回，当然参数可以任意多个，它不支持任何的命令，除了默认的return之外。还有一点lambda函数本身永远为真，当然返回值可以任意。
13.python中类的概念，有点类似共享存储区的意思，所有的属性还有方法只有一份，只不过可以有多个实例来使用，它的类还支持一些专有方法，主要目 的是实现各种类的通用操作，有点类似java中由object继承下来的基本方法，但是，python并不是要求所有类都必须有这几个方法，当然如果你实 现了的话，操作起来会更加统一，都跟列表的操作类似。
14.python中还有个地方很像java就是它也提供了封装类，就像java中对基本数据类型做得一样，python也把它的基本类型列表，元组，字典都给封装成了类UserList,UserString,UserDict。
15.python中也支持public 和 private 但是没有friend,所有以两个连续的下划线开头，但结尾不是两个连续的下划线的属性还有方法都是private。
16.一些python教程的地址
http://cn.diveintopython.org/                        dive into python
http://www.byteofpython.info/language/chinese/index.html 简明python教程
http://docs.python.org/tut/tut.html                 python tutorial
http://www.python.org/doc/current/ref/       python reference manual
http://www.python.org/doc/current/lib/        python library reference
17.这是个用java写的解释器，可以在里面调用java api，还没有用过。
http://www.jython.org/

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__(两个下划线连在一起)属性,来展现出来.
11.python的数据结构比较有特色，当然我所说的时基本数据结构，它包括三个基本数据结构，列表，元组，字典，列表比较类似数组，元组则不可以被改 变，字典有点类似java中的hashmap主要是key:value的匹配对。三种数据结构都用到序列，所以都可一通过［］来访问，列表是由［］声明， 元组是（）声明，字典是｛｝声明，字典里面的键值要用简单的对象来实现。什么是序列呢，他主要的特点就是支持分片操作符还有游标操作符，其中许多方法与 java中的字符串的方法相类似。
12.python中也不存在指针，跟java一样，支持引用。
13.python中类的声明跟java差不多，也支持public and private，是通过在变量前是否有两个连续的下划线区分的，__init__类似c++中的构造函数，self跟
java,c++中的this相同，__del__类似c++中的析构函数，也支持继承，但是继承的时候有个地方需要注意，子类的构造函数并不默认的调用父类的构造函数，这需要你自己来显示调用。
14.输入输出中的文件操作，出了普通的功能外还有一个特点，就是可以指定文件的权限，也就是，是只读还是读写。它还提供一种存储器，可以想里面存放任何 对象，存储器是pickle和cPickle，后者是用c语言实现的，所以十分的高效，据称比pickle快1000倍，主要就是把任何一个对象与文件联 系到一起，支持两个操作dump,pop。
15.python中的模块就跟java,c++,c中类库的概念一样，相比之下与java共同点更多，支持import 和import as 和 from ... import 三种形式，第一种与java中的import一样，第二种相当于别名，也就是import xyz as x 用x 来代替xyz,第三种类似java中import java.util.scanner这样的操作，也就是可以指定模块中的元素。dir()函数可以列出模块的所有元素。
16.python中的异常机制非常类似java,也可以声明自己定义的异常类，与java中try catch finally相对应的是try except finally
17.python中有个assert()函数与c++中的assert()函数一样。
18.列表综合是一种非常有效的手段，直观上看去就是把一个for循环加入到一个列表的声明中去。
19.python支持函数的参数为元组和字典，相应的需要操作符*,**；＊把多余的参数存为元组，**则存为字典。
20.exec可以执行报存在字符串或者文件中的python命令，eval则能计算保存在字符串中的表达式的值。

刘鑫的Blog:http://80x86.cn/blog/
rpm search:http://rpm.pbone.net
live cd:http://gentoo-wiki.com/HOWTO_build_a_LiveCD
packages:http://packages.gentoo.org
fedora project:http://fedora.linuxsir.org/main