字符串匹配

          我想了好几天字符串匹配算法.现在市面上卖的有这么几种:

    蛮力:BruteForce; KMP ; BM ; Hospool ; Sunday.

    不加详解,只做点评.

    蛮力:双重for循环,自然朴实,简单雅致.

    KMP:实际上我一直想说一句话:没学计算机专业的人都选错专业了.其实KMP的祖宗是有限状态自动机,每一个句子都对应一个有限状态自动机.现在看到的KMP是化简了的Express版,Professional版是一个二维的next数组,而不是一维的next.当失配的时候,会根据具体字符决定跳转.

     BM,Sunday倒骑毛驴,倒着走比正着走快.比如欧阳锋.

     Sunday效率好,算法简单,KMP弱爆了.但是KMP是一种思想,博大精深,它首先突破了传统的蛮力.

     下面讲一下代码,KMP的GetNext.

   

void getNext(char*p, int *next){
	int i = next[0]=-1, j = 0;
	while (p[j] != 0){
		if (i == -1 || p[j] == p[i]){
			j++; i++;//前进
			next[j] = i;//赋值只在此处发生
		}
		else i = next[i];//i向前回溯
	}
}
/*i 是来来回回漂泊不定,它就是next[]将要等于的值.
   j是单向移动的东西,它是next的下标
   最难理解的是那个if语句
   i==-1表示后无退路了,只得前进
   p[i]==p[j]表示前途无量,一帆风顺,所以前进.
   只有在p[i]!=p[j]并且后面有路可退的时候才能执行else进行回溯.
  */