leetcode――Implement strStr() 实现字符串匹配函数（AC）

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

这个题考查的是KMP算法，先求特征向量，然后再进行匹配，确实可以大大提高效率。code如下：

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        if(strlen(haystack)==0&&strlen(needle)==0)
            return haystack;
        if(strlen(haystack)==0&&strlen(needle)!=0)
			return NULL;
		if(strlen(needle)==0)
		    return haystack;
		int m=strlen(needle);
        int *N = new int[m];
		N[0]=0;
		int i,j,k;
		for(i=1;i
  
   0 && needle[i]!=needle[k])
			{
				k=N[k-1];
			}
			if(needle[i]==needle[k])
				N[i]=k+1;
			else
				N[i]=0;
		}
		j=0;
		for(i=0;i
   
    0 && needle[j]!=haystack[i]) j=N[j-1]; if(needle[j]==haystack[i]) j++; if(j==strlen(needle)) return haystack+i-j+1; } return NULL; } };