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;
}

--