LeetCode之Implement strStr()

本题是LeetCode28题，属于Easily级别

给出题目描述

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02): The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button  to reset your code definition.

实质就是一个字符串首次匹配问题

相信大家肯定都知道BF（Brute-Force）以及KMP算法，这里就不再说多余的累赘的细节来阐述这两个算法，而是从另一个角度来感性的认识一下这两个算法

BF算法：

S：aaaachtr

P：aaac

这里可以发现前三位都是匹配的，但是最后一位不匹配，匹配的过程是S的i从0-3，P的j从0-3，失败了，很失望，最直观的想法就是我的S从下一个字符开始匹配

（多数保守派童鞋都是这么干的，很不幸，本人也是保守派）

S：aaaachtr

P：  aaac

但是社会总有一些激进青年，他们总能想出一条捷径，然后 他们就完成了变革，下面就让我们看一下KMP的激进思想

KMP算法：

核心思想就是当匹配不成功时，下一次匹配的位置能否只改变P的位置，而S不发生回溯（打破保守派）

最激进的童鞋提出了自己的方案（很不幸，本人从保守派转型时也是这么干的）

S：aaaachtr

P：aaac

当匹配不成功时，S位置i保持不变，P位置从j位置变为0

S：aaaachtr

P：       aaac

很明显，这位激进派的同学太有热情了，直接抛弃了以前匹配成功的（在他的潜意识中认为S匹配成功的 “aaa”已经没用了，可以扔掉了）

但是事实证明了，扔掉这一部分导致他改革失败了（力度过大了）

所以下次匹配的位置还需要仔细的斟酌一下，而不是如此的鲁莽

这样的位置才是我们想要的！！！！

S：aaaachtr

P：  aaac

P直接向后回溯了一个位置，回到了j=2的位置上，此时i=3，然后S[i]=P[j]='a'，然后S[i+1]=P[j+1]='c'，然后就没有然后了

因此的话，发现，要改革成功，必须要知道P中某一个位置当匹配不成功时，P往前回溯的下一个位置！

大家把改革的重点放在了P上，这里我们用一个next数组存放P中每一个位置匹配不成功时的下次回溯的位置

只看P：aaac（感性的认识一下）

P1：aaa

P2：  aac

大家发现这两个字符串怎么这么像，对（组合在一起就是aaac），P1[0,1]=P2[0,1],P1[2]!=P2[2]，如果aac中的c匹配不成功，我能否把位置调整到aaa最后的位置看能够匹配

（万一要是S中就是aaa的话，那就太好了，这就和P1匹配上了），其实P1就是P中的一个子串，有一个优雅的名字叫做前缀，P2也有一个优雅的名字叫做后缀

因此如果能够找到这样的前缀和后缀，当后缀匹配不成功时，就转到前缀对应的位置去匹配（试试运气）

那现在的重点就是放在找前缀和后缀上

当P匹配到a时失败（一个字符有前缀和后缀吗，如果前后缀相同就是本身的话，岂不是死循环）

因此a的next[0]就是-1，一旦是是-1的话，就表示没有想要的子串（P和S必须同时向右移动重新从头匹配）

当P匹配到aa时失败（a和a分别是前缀和后缀）

如果后缀的a匹配不成功，那么前缀的a也肯定不成功，因此后缀a的next[1]就是前缀a的next[0]，即next[1]=next[0]

（然后前缀a怎么的就不管了，因为前缀a已经有了next[0]了）

当P匹配到aaa时失败(前缀就是aa，后缀就是aa)

如果后缀的aa匹配不成功，那么前缀的aa肯定也匹配不成功，因此后缀aa中最后一个a的next就是前缀aa中最后一个a的next

即next[2]=next[1]

当P匹配到aaac时失败（前缀就是aaa，后缀就是aac）

如果后缀aac不匹配，那么前缀aaa是可能匹配的(WHY?????)

aac不匹配只因为c，如果正确的匹配字符就是a的话，那么就是aaa了，

那如果正确的字符还不是a呢，那就没什么好说的了，P的下次匹配的位置继续向前回溯

此时的j=next[j]（位置j就变成了前缀aaa中最后一个字符a的next[j]了）

给出next=[-1,0,0,2]

有点绕晕了吧，多想想，肯定会感同身受的！！！

有了next，那么P和S匹配的时候是如此的easy了，为了加深大家的印象，在模拟一遍P和S的匹配过程

Step1:

S：aaaachtr

P：aaac

不匹配，哦，我们有了next，此时的i=3，j=3,next[j]=2

那么j=next[j]=2了，P向前回溯的位置就是j=2

Step2:

S：aaaachtr

P：  aaac

Step3:

S：aaaachtr

P：  aaac

没有然后了，匹配成功了。

KMP算法就到此结束了，按照这种思想是不是就能完成LeetCode上的字符串首次匹配了呢

贴出源代码(参考了网上关于KMP算法的一些代码)

class Solution {
public:
void getNext(char *p,int next[])
{
	int i=-1,j=0;
	int len=strlen(p);
	next[0]=-1;
	while(j<len-1) {

		if(i==-1 || p[i]==p[j]) {
			i++,j++;
			//下一个字符不匹配
			if(p[i]!=p[j])
				next[j]=i;
			else
				next[j]=next[i];
		}
		//当前字符不匹配，转到下一个匹配位置
		//和j位置看能否构成匹配
		else
			i=next[i];
	}
}

int strStr(char *haystack, char *needle) 
{
	if(haystack==NULL || needle==NULL)
		return -1;
	else if(needle[0]=='\0')
		return 0;
	//起始匹配的位置
	int len2=strlen(needle),len1=strlen(haystack);
	//len2长度大于len1
	if(len2>len1)
		return -1;
	int *next=new int[len2];
	//获得next
	getNext(needle,next);
	int i=0,j=0;
	//匹配
	while(i<len1 && j<len2) {

		if(j==-1 || haystack[i]==needle[j])
			i++,j++;
		else
			j=next[j];
	}
	delete []next;
	//子串全部匹配完
	if(j>=len2)
		return i-len2;
	return -1;
}
};

Accepted截图

发现这种方法是不是效率很高，有兴趣同学可以试试。

最后本人也是一直在做LeetCode，所有Problems的代码都开源了，并且都是Accepted过的

项目地址git@code.csdn.net:yiranyaoqiu/leetcode_problems.git

有兴趣同学可以参考其中另外的一些Problems。