leecode-C语言实现-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

解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10**4

• haystack 和 needle 仅由小写英文字符组成

二、解题思路

这里可以用两种方法进行解题，一种是BF算法（暴力搜索算法），算法时间复杂度为O(n*m)，另一种是KMP算法（BF算法改进），算法时间复杂度为O(n+m)。这里我们用KMP算法进行解题，最好结合着《三、函数介绍》来看。

在进行字符串匹配之前，我们需要算出模式串的前缀表，也就是算出模式串从第一个字符到倒数第二字符的最长公共前后缀。如下图：

我们可以根据第一个A来推导AB,再来推导ABA的最长公共前后缀，推导方法为：

1. A只有一个，最长公共前后缀：0。

2. AB，新增字符B，A和B不相等，最长公共前后缀：0。

3. ABA，新增字符A，A和A相等，最长公共前后缀：1。

4. ABAB，新增字符B，B和B（上一个最长公共前后缀：1为索引位的值为B）相等，最长公共前后缀：2。

5. ABABC，新增字符C，C和A（上一个最长公共前后缀：2为索引位的值为A）不相等，这时需要计算前两位AB和后两位BC是否相等，不相等，最长公共前后缀：0。

6. ABABCA，新增字符A，A和A（上一个最长公共前后缀：0,所以直接和头部的A比较）相等，最长公共前后缀：1。

7. ABABCAB，新增字符B，B和B（上一个最长公共前后缀：1为索引位的值为B）相等，最长公共前后缀加一变为：2。

8. ABABCABA，新增字符A，A和A（上一个最长公共前后缀：2为索引位的值为A）相等，最长公共前后缀加一变为：3。

再在前缀表的前面加-1主要是为了方便计算，就到了最终版前缀表。

前缀表PrefixTable，主串索引PrimaryStrIndex，模式串索引SubStrIndex，从0开始匹配，当匹配到4号索引位时和主串字符不同，SubStrIndex由4变为PrefixTable[4]也就是2，模式串的2号索引位为A，相等和主串索引4号位A，继续匹配。

当匹配到PrimaryStrIndex=6，SubStrIndex=4时，又不想等，将SubStrIndex置为PrefixTable[4]也就是2，模式串的2号索引位为A，相等和主串索引6号位A，继续匹配，发现全部匹配上，就OK了。

三、函数介绍

1、GetPrefixTable

（1）用途

给出字符串StrArray及其长度StrArrayLen，返回一个int类型的前缀表数组。

（2）源码

int* GetPrefixTable(char* StrArray, size_t StrArrayLen)
{int* PrefixTable        = (int*)malloc(sizeof(int) * StrArrayLen);PrefixTable[0]          = -1;if(StrArrayLen == 1){return PrefixTable;}PrefixTable[1]          = 0;size_t StrArrayIndex    = 1;size_t PrefixTableIndex;size_t i = 0;for(PrefixTableIndex = 2; PrefixTableIndex<StrArrayLen; PrefixTableIndex++,StrArrayIndex++){//printf("PrefixTableIndex : %ld, StrArrayIndex : %ld, PrefixTable[PrefixTableIndex-1] : %d\n",PrefixTableIndex,StrArrayIndex,PrefixTable[PrefixTableIndex-1]);if(PrefixTable[PrefixTableIndex-1] == 0) //如果前缀表的上一位的值为0，说明没有公共前后缀。{//printf("StrArray[0] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[0], StrArray[StrArrayIndex]);if(StrArray[0] == StrArray[StrArrayIndex]) //判断第一个字符和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] = 1;}else{PrefixTable[PrefixTableIndex] = 0;}}else{//printf("StrArray[PrefixTable[PrefixTableIndex-1]] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[PrefixTable[PrefixTableIndex-1]],StrArray[StrArrayIndex]);if(StrArray[PrefixTable[PrefixTableIndex-1]] == StrArray[StrArrayIndex])//判断上一个公共前缀最大长度的后一位和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1] + 1;}else{for(i=0; i<PrefixTable[PrefixTableIndex-1]; i++)//需要循环判断上一个公共前缀的每个字符和新子串的相应字符是否相等。如果上一个公共前缀最大长度是2，字符串aacaaa,那就需要判断前两个a和后两个a是否相等。{if(StrArray[i] != StrArray[StrArrayIndex-PrefixTable[PrefixTableIndex-1]+1+i]){PrefixTable[PrefixTableIndex] = 0;break;}}if(i == PrefixTable[PrefixTableIndex-1]){PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1];}}}//printf("PrefixTable[%ld] = %d\n",PrefixTableIndex,PrefixTable[PrefixTableIndex]);//printf("=====================\n");}return PrefixTable;
}

（3）参数

参数名	描述
StrArray	char*类型StrArray字符串。
StrArrayLen	size_t类型的StrArray长度。

2、KmpSearch

（1）用途

在主串PrimaryStr搜索第Times次出现的模式串SubStr，返回SubStr的首字符在PrimaryStr的索引位。如果匹配失败返回-1。

（2）源码

int KmpSearch(char* PrimaryStr, char* SubStr, int Times)
{if(PrimaryStr == NULL || SubStr == NULL){return -1;}if(Times < 1){return -1;}size_t      PrimaryStrLen = strlen(PrimaryStr);size_t      SubStrLen     = strlen(SubStr);if(SubStrLen > PrimaryStrLen){return -1;}else if(SubStrLen == PrimaryStrLen){if(strcmp(SubStr,PrimaryStr) == 0){return 0;}else{return -1;}}long long PrimaryStrIndex = 0;long long SubStrIndex     = 0;int Cnt                   = 0;//匹配次数和Times对应。 int* PrefixTable          = GetPrefixTable(SubStr, SubStrLen);PrintArray(PrimaryStr, PrimaryStrLen, sizeof(char));PrintArray(SubStr, SubStrLen, sizeof(char));PrintArray(PrefixTable, SubStrLen, sizeof(int));while(PrimaryStrIndex < PrimaryStrLen){if(PrimaryStr[PrimaryStrIndex] == SubStr[SubStrIndex]){PrimaryStrIndex++;SubStrIndex++;if(SubStrIndex == SubStrLen){Cnt++;if(Cnt == Times){return PrimaryStrIndex - SubStrIndex;}SubStrIndex--;SubStrIndex = PrefixTable[SubStrIndex];}}else{SubStrIndex = PrefixTable[SubStrIndex];if(SubStrIndex == -1){PrimaryStrIndex++;SubStrIndex++;}}}free(PrefixTable);return -1;
}

（3）参数

参数名	描述
PrimaryStr	char*类型主串。
SubStr	char*类型模式串。
Times	匹配第几次

四、虚机测试源码

# include<stdio.h>
# include<string.h>
# include<stdlib.h>int* GetPrefixTable(char* StrArray, size_t StrArrayLen);
int KmpSearch(char* PrimaryStr, char* SubStr, int Times);
void PrintArray(void* Array, size_t ArrayLen, size_t TypeFlag);int main()
{char* PrimaryStr = "ABABABABCABAAB";char* SubStr     = "ABABCABAA";printf("Position : %d\n",KmpSearch(PrimaryStr, SubStr, 1));return 0;
}int* GetPrefixTable(char* StrArray, size_t StrArrayLen)
{int* PrefixTable        = (int*)malloc(sizeof(int) * StrArrayLen);PrefixTable[0]          = -1;if(StrArrayLen == 1){return PrefixTable;}PrefixTable[1]          = 0;size_t StrArrayIndex    = 1;size_t PrefixTableIndex;size_t i = 0;for(PrefixTableIndex = 2; PrefixTableIndex<StrArrayLen; PrefixTableIndex++,StrArrayIndex++){//printf("PrefixTableIndex : %ld, StrArrayIndex : %ld, PrefixTable[PrefixTableIndex-1] : %d\n",PrefixTableIndex,StrArrayIndex,PrefixTable[PrefixTableIndex-1]);if(PrefixTable[PrefixTableIndex-1] == 0) //如果前缀表的上一位的值为0，说明没有公共前后缀。{//printf("StrArray[0] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[0], StrArray[StrArrayIndex]);if(StrArray[0] == StrArray[StrArrayIndex]) //判断第一个字符和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] = 1;}else{PrefixTable[PrefixTableIndex] = 0;}}else{//printf("StrArray[PrefixTable[PrefixTableIndex-1]] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[PrefixTable[PrefixTableIndex-1]],StrArray[StrArrayIndex]);if(StrArray[PrefixTable[PrefixTableIndex-1]] == StrArray[StrArrayIndex])//判断上一个公共前缀最大长度的后一位和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1] + 1;}else{for(i=0; i<PrefixTable[PrefixTableIndex-1]; i++)//需要循环判断上一个公共前缀的每个字符和新子串的相应字符是否相等。如果上一个公共前缀最大长度是2，字符串aacaaa,那就需要判断前两个a和后两个a是否相等。{if(StrArray[i] != StrArray[StrArrayIndex-PrefixTable[PrefixTableIndex-1]+1+i]){PrefixTable[PrefixTableIndex] = 0;break;}}if(i == PrefixTable[PrefixTableIndex-1]){PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1];}}}//printf("PrefixTable[%ld] = %d\n",PrefixTableIndex,PrefixTable[PrefixTableIndex]);//printf("=====================\n");}return PrefixTable;
}int KmpSearch(char* PrimaryStr, char* SubStr, int Times)
{if(PrimaryStr == NULL || SubStr == NULL){return -1;}size_t      PrimaryStrLen = strlen(PrimaryStr);size_t      SubStrLen     = strlen(SubStr);if(SubStrLen > PrimaryStrLen){return -1;}else if(SubStrLen == PrimaryStrLen){if(strcmp(SubStr,PrimaryStr) == 0){return 0;}else{return -1;}}long long PrimaryStrIndex = 0;long long SubStrIndex     = 0;int Cnt                   = 0;//匹配次数和Times对应。 int* PrefixTable          = GetPrefixTable(SubStr, SubStrLen);PrintArray(PrimaryStr, PrimaryStrLen, sizeof(char));PrintArray(SubStr, SubStrLen, sizeof(char));PrintArray(PrefixTable, SubStrLen, sizeof(int));while(PrimaryStrIndex < PrimaryStrLen){if(PrimaryStr[PrimaryStrIndex] == SubStr[SubStrIndex]){PrimaryStrIndex++;SubStrIndex++;if(SubStrIndex == SubStrLen){Cnt++;if(Cnt == Times){return PrimaryStrIndex - SubStrIndex;}SubStrIndex--;SubStrIndex = PrefixTable[SubStrIndex];}}else{SubStrIndex = PrefixTable[SubStrIndex];if(SubStrIndex == -1){PrimaryStrIndex++;SubStrIndex++;}}}free(PrefixTable);return -1;
}void PrintArray(void* Array, size_t ArrayLen, size_t TypeFlag)
{size_t i;printf("Array    : ");for(i = 0; i < ArrayLen; i++){switch(TypeFlag){case sizeof(int)  : printf("%d ",((int*)Array)[i]); break;case sizeof(char) : printf("%c ",((char*)Array)[i]); break;default : printf("Unknow Type!!!\n" );}}printf("\n==================================\n");
}

五、虚机测试

[gbase@czg2 LinearTable_String_KMP]$ make
gcc -Wall -g KmpSearch.c -o Test_KmpSearch [gbase@czg2 LinearTable_String_KMP]$ ./Test_KmpSearch 
Array    : A B A B A B A B C A B A A B 
==================================
Array    : A B A B C A B A A 
==================================
Array    : -1 0 0 1 2 0 1 2 3 
==================================
Position : 4

六、Leecode提交源码

int* GetPrefixTable(char* StrArray, size_t StrArrayLen);
int KmpSearch(char* PrimaryStr, char* SubStr, int Times);int strStr(char * haystack, char * needle){return KmpSearch(haystack, needle, 1);
}int* GetPrefixTable(char* StrArray, size_t StrArrayLen)
{int* PrefixTable        = (int*)malloc(sizeof(int) * StrArrayLen);PrefixTable[0]          = -1;if(StrArrayLen == 1){return PrefixTable;}PrefixTable[1]          = 0;size_t StrArrayIndex    = 1;size_t PrefixTableIndex;int i = 0;for(PrefixTableIndex = 2; PrefixTableIndex<StrArrayLen; PrefixTableIndex++,StrArrayIndex++){//printf("PrefixTableIndex : %ld, StrArrayIndex : %ld, PrefixTable[PrefixTableIndex-1] : %d\n",PrefixTableIndex,StrArrayIndex,PrefixTable[PrefixTableIndex-1]);if(PrefixTable[PrefixTableIndex-1] == 0) //如果前缀表的上一位的值为0，说明没有公共前后缀。{//printf("StrArray[0] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[0], StrArray[StrArrayIndex]);if(StrArray[0] == StrArray[StrArrayIndex]) //判断第一个字符和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] = 1;}else{PrefixTable[PrefixTableIndex] = 0;}}else{//printf("StrArray[PrefixTable[PrefixTableIndex-1]] : %c, StrArray[StrArrayIndex] : %c\n",StrArray[PrefixTable[PrefixTableIndex-1]],StrArray[StrArrayIndex]);if(StrArray[PrefixTable[PrefixTableIndex-1]] == StrArray[StrArrayIndex])//判断上一个公共前缀最大长度的后一位和新子串最后一位是否相等。{PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1] + 1;}else{for(i=0; i<PrefixTable[PrefixTableIndex-1]; i++){if(StrArray[i] != StrArray[StrArrayIndex-PrefixTable[PrefixTableIndex-1]+1+i]){PrefixTable[PrefixTableIndex] = 0;break;}}if(i == PrefixTable[PrefixTableIndex-1]){PrefixTable[PrefixTableIndex] =  PrefixTable[PrefixTableIndex-1];}}}//printf("PrefixTable[%ld] = %d\n",PrefixTableIndex,PrefixTable[PrefixTableIndex]);//printf("=====================\n");}return PrefixTable;
}int KmpSearch(char* PrimaryStr, char* SubStr, int Times)
{if(PrimaryStr == NULL || SubStr == NULL){return -1;}size_t      PrimaryStrLen = strlen(PrimaryStr);size_t      SubStrLen     = strlen(SubStr);if(SubStrLen > PrimaryStrLen){return -1;}else if(SubStrLen == PrimaryStrLen){if(strcmp(SubStr,PrimaryStr) == 0){return 0;}else{return -1;}}long long PrimaryStrIndex = 0;long long SubStrIndex     = 0;int Cnt                   = 0;//匹配次数和Times对应。 int* PrefixTable          = GetPrefixTable(SubStr, SubStrLen);//PrintArray(PrimaryStr, PrimaryStrLen, sizeof(char));//PrintArray(SubStr, SubStrLen, sizeof(char));//PrintArray(PrefixTable, SubStrLen, sizeof(int));while(PrimaryStrIndex < PrimaryStrLen){if(PrimaryStr[PrimaryStrIndex] == SubStr[SubStrIndex]){PrimaryStrIndex++;SubStrIndex++;if(SubStrIndex == SubStrLen){Cnt++;if(Cnt == Times){return PrimaryStrIndex - SubStrIndex;}SubStrIndex--;SubStrIndex = PrefixTable[SubStrIndex];}}else{SubStrIndex = PrefixTable[SubStrIndex];if(SubStrIndex == -1){PrimaryStrIndex++;SubStrIndex++;}}}free(PrefixTable);return -1;
}void PrintArray(void* Array, size_t ArrayLen, size_t TypeFlag)
{size_t i;printf("Array    : ");for(i = 0; i < ArrayLen; i++){switch(TypeFlag){case sizeof(int)  : printf("%d ",((int*)Array)[i]); break;case sizeof(char) : printf("%c ",((char*)Array)[i]); break;default : printf("Unknow Type!!!\n" );}}printf("\n==================================\n");
}

七、Leecode通过截图