28找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1
解题思路：KMP算法。不相等j回退到前一个位置的next[j-1],相等j++;next[i]=j;
具体步骤如下
m为匹配串p长度，n为要匹配的长串s长度
1、确定前缀表next的值，初始化next[0]=0
j为前缀末尾，i为后缀末尾，初始j=0,i=1
for(i=1;i<m;i++){
while(j>0&&p[i]!=p[j])j=next[j-1];//回退冲突的前一个位置
if(p[i]==p[j])j++;
next[i]=j;
}
2、匹配过程
for(i=0,j=0;i<n;i++){
while(j>0&&s[i]!=p[j])j=next[j-1];
if(s[i]==p[j])j++;
if(j==m)return i-m+1;
}
int strStr(char* haystack, char* needle) {int n=strlen(haystack),m=strlen(needle);if(m==0)return 0;int *next=(int *)malloc(sizeof(int)*(m+1));next[0]=0;//初始化int i,j=0;//i为后缀末尾，j为前缀末尾i//处理next数组，回退到冲突前一个nextfor(i=1;i<m;i++){//前后缀不相同,此处是whilewhile(j>0&&needle[i]!=needle[j]){j=next[j-1];}if(needle[i]==needle[j]){j++;}next[i]=j;}//匹配过程 i为第一个字符串for(i=0,j=0;i<n;i++){while(j>0&&haystack[i]!=needle[j])j=next[j-1];if(haystack[i]==needle[j])j++;if(j==m)return i-m+1;}return -1;
}--
