字符串匹配

一叶飞刀

关于字符串匹配，应当已经解决完毕了，大概不会有更高级的算法了。
4 V& u& K7 e4 l- w6 K# d7 C5 ]- g
从S中找ss简单匹配算法为用ss的第一个字母对齐S，逐一比对，直到不匹配或者完全匹配，然后ss的第一个字母对齐S的第二个字母，如此反复，算法复杂度为S和ss长度的乘积，即无论哪个字符串长度增加一倍，执行时间大体增加一倍。
  I' ^) Q2 I0 R, h
2 N; D6 s/ h: m* P4 A: K6 U# ]高级算法是，既然以前已经比较过了，那么后面的比较就可以利用前面失败的匹配所收集的信息，从而下次匹配时直接往前跳，比如一开始从S的第一个字符跟ss的第一个字符比对，比对到第十个字符，失配，那么由于已经进行了九个字符的匹配且能对的上，那么以前已经匹配过的九个字符就不要重复匹配了，第十个字符根据某种规则直接跟ss中的某一个字符匹配。这种算法的复杂度为S的长度。由于要匹配，至少要遍历S一次，所以这个最多在细节上改进，不会有本质的改进。
* f7 V1 c3 Y, F3 ~, S/ z
2 H' ^' N7 q  H; k  [. K8 A以上，任何一本数据结构教材，比如清华版的数据结构与算法，均有提及