这是今天的第三题了，也是leetcode第28题，算法的难度也是easy，但字符串匹配这个问题本身是一个非常重要的问题。而其算法有相对简单的，有比较难的，今天我们来讲一个比较有深度的方法。当然，算法难了肯定是有时间复杂度的好处的，正所谓无利不起早嘛。好了，还是先看题目吧

Implement strStr().

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

题目有几个难理解的单词，所以还是翻译一下吧：实现strStr()函数，如果主字符串中有子字符串则返回子字符串第一次在主字符串中出现的下标，如果没有，则返回-1。（如还不明白请百度strstr）

这是一个很典型的字符串匹配问题，它还有一个上档次的名字叫做模式匹配。相对应的那个子串叫做模式串。

题目有个非常简单粗暴的解法，我不说大家也能想到，就是把主串第一个和模式串第一个对其，看是否能匹配，如果不匹配再把主串第二个和模式串第一个对其，如果还不匹配再看第三个……这样做显然是不太高明的，时间复杂度为O(m*n)。

那该怎么改进这个算法呢？一般人还真没什么好办法，不过大神是有的，KMP算法就是解决模式匹配问题的经典算法之一。这个算法逻辑比较复杂，我们慢慢道来。

我们先来看一下上面的蛮力法是怎么做的，我们用两个下标（暂且叫做i和j吧）分别指向主串的起始位置和模式串的起始位置，然后就是一个一个比较了，如果这两个元素相同，那就把这两个下标都后移（i++,j++）。如果这两个算是不同，则j回到模式串的起始位置，而i则回到刚才起始位置的下一个位置。

现在我们来提出改进思路，相同的时候往后移这个肯定是不能变的，也没啥可改进的。关键是当两个元素不同的时候，为了说明问题，我们举个例子说明：假如主串是“abababcacbab”，模式串是“abcac”。用传统方法：第一次匹配i=2，j=2时，由于主串中为a而子串中为c所以匹配失败，则i回到1，j回到0。这个显然不行，所以i变成2（j还是0）继续匹配。当i=4，j=2时，又出现了不匹配的情况，所以i回到3，j回到0……通过观察可发现（当然是大神的观察），每次匹配失败时i回退的很多，这是没有必要的，因为i前面一段已经成功匹配了，也就是说i前面一段和j前面一段是相匹配的。那么假如i回退，就会出现模式串j前面那段自己和自己比的过程，而且这个过程在整个匹配过程中反复多次进行。

那么，能否现将模式串自己和自己比，得到一个比较结果，等真的模式匹配的时候可以直接查询结果而不多次比较呢？由于匹配失败时i前面匹配的部分全部都在模式串中，所以可以推测i在比较过程中不用回退，只要将j回退到合适位置即可。回退的结果是模式串的新的j前面的那部分是和主串中i前面那部分相匹配的。

这个新j的位置我们用一个数组来表示，假如a[x]=y，则说明如果j=x时匹配失败，则j应该回退到y处。我们给这个数组起个名字叫next，以示j的下一个取值的功能。

我们先来看看这个数组怎么得到：正如前面说的说的，数组里放的是当前位置匹配失败后j应该回退的位置，这样一来那第一个（下标0）位置肯定应该放0，以示当第一个元素匹配失败时j还应该从下标0开始，从第二个开始，我们确定其值是应该这么考虑，假设前k-1个位置已经填好了，现在填第k个。填第k个要参考第k-1个，因为k-1个表示的是，next[k-1]表示的是什么呢？我们这样来看，假如next[k-1]=t，那表示从0到t-1这t个数是和k-1前面的t个数相同的，所以现在应该看str[t]是否等于str[k-1]如果相等，那说明从0到t这t+1个数是和k前面的t+1个数匹配的。所以next[k]应该为t+1，级next[k-1]+1。如果不相等，那说明str[t]和第k个前面的字符不匹配，则再继续向前匹配，知道找到一个下标m，使得从0到m这个范围内的字符和k前面m个字符相等，或者退到起始位置。（这个过程真是不好说明白，大家多在纸上画一画最好）

还是来看代码吧：

void getNextArr(const string& str,const string::size_type n,int next[])
{
	next[0]=-1;//先将第一个设为-1作为停止哨兵
	for(string::size_type i = 1;i<n;i++){
		int j = next[i-1];
		while(j != -1)
		{
			if(str[j]==str[i-1]) {
				next[i]=j+1;break;				
			}
			else{
				j=next[j];
			}
		}
		if(j==-1) next[i]=0;
	}
	next[0]=0;
}

class Solution {
public:
    int strStr(string haystack, string needle) {
		string::size_type hLen = haystack.size();
		string::size_type nLen = needle.size();
		if(hLen==0 || nLen==0) return -1;
		int *nxt = new int[nLen];
		getNextArr(needle,nLen,nxt);
		string::size_type i = 0;
		string::size_type j = 0;
		while(i<hLen && j<nLen)
		{
			if(haystack[i]==needle[j]){
				i++;j++;
			}
			else{
				j=nxt[j];
				if(j==0 && haystack[i]!=needle[j]) 				{
					i++;
				}
			}
		}
		delete[] nxt;
		if(j==nLen) return i-nLen;
		else return -1;		
    }
};