前几天，有个朋友问我关于复杂度为O(n)的最大回文串算法（longest palindromic substring）的问题，这个算法平时用的不多，但是一两年前接触这个算法的时候印象颇深，于是给他由简到繁地讲解了一遍，兴之所至，想把关于这个算法的一些心得总结一下，留作备份，而算法原理不多赘述。因为其间涉及了一点简单的Brute Force字符串模式匹配算法，所以先简单说说字符串模式匹配算法。
字符串模式匹配算法（string searching/matching algorithms），顾名思义，就是在一个文本或者较长的一段字符串中，找出一个或多个指定字符串（Pattern），并返回其位置。这类算法属基础算法，各种编程语言都将其包括在自带的String类函数中，而且由之衍生出来的正则表达式也是必须掌握的一种概念和编程技术。
最简单的是Brute-Force算法，其思路很简单：从目标字符串初始位置开始，依次分别与Pattern的各个位置的字符比较，如相同，比较下一个位置的字符直至完全匹配；如果不同则跳到目标字符串下一位置继续如此与Pattern比较，直至找到匹配字符串并返回其位置。
代码也很简单，如下所示(Java)：
public Class Brute-Force{//written by Yimengpublic static int BruteForce(String source,String sub){int source_index=0,sub_index=0,index=-1;while((source_index<source.length())&&(sub_index<sub.length())){if(source.charAt(source_index)==sub.charAt(sub_index)){source_index++;sub_index++;}else{source_index=source_index-sub_index+1;sub_index=0;}if(sub_index==sub.length()) return source_index-sub_index;}return -1;}}
设目标串的长度为m，Pattern的长度为n，不难得出BF算法的时间复杂度为O(mn)，效率很低，于是便产生了改进的KMP算法。
Knuth–Morris–Pratt算法在BF算法的基础上使用next函数来找出下一次目标函数与Pattern比较的位置，因为BF算法每次移动一位的比较是冗余的，KMP利用Pattern字符重复的特性来排除不必要的比较，从而可以每次移动n位来排除冗余。
我写的代码如下所示，核心是next[]数组的得出方法：
public static int KMP(String s,String sub){//written by Yimengint m=0,n=0;int[] next=new int[sub.length()];KMPtable(sub,next);while(m+n<s.length()){if(s.charAt(m+n)==sub.charAt(n)){if(n==sub.length()-1) return m;n++;}else{m=m+n-next[n];if(next[n]!=-1) n=next[n];else n=0;}}return -1;}private static void KMPtable(String sub,int[] next){int pos=2,i=0;next[0]=-1;next[1]=0;while(pos<sub.length()){if(sub.charAt(pos-1)==sub.charAt(i)){i++;next[pos]=i;pos++;}else if(i>0) i=next[i];else{next[pos]=0;pos++;}}}
KMP算法的时间复杂度为O(m+n)，为线性阶，较BF效率高得多。
此外，其他比较有名的模式匹配算法，如Boyer–Moore、Horspool算法、Sunday算法、Rabin–Karp算法、Commentz-Walter算法等等，不一而足。大多数知其然即可，要用的时候再掌握，如果不是PHD，在找工作和日常工作学习中基本不会遇到。个人认为字符串模式匹配算法，身为软件工程师，不管用不用，对KMP都一定要倒背如流，如果要求再高一点，BM和RK要知其所以然。
当然，字符串模式匹配的应用比其算法本身重要得多。如果String Searching algorithms和Regular Expression只会一样，建议选择后者。引文你可能一辈子只在面试是会写一遍KMP算法，但你可能一天都离不开正则表达式。如果你声称能熟练使用Linux命令行，流利掌握PHP或者Perl，对算法运用行云流水，而却不懂正则表达式，就像一个精通编程的“码工”不会双手使用Vim一样。
最后，想到一个检验正则表达式掌握程度的算法题：给你段押尾韵不分行的英文诗，你可以设计一个算法，把它分行吗？@沂濛
文章评论