找出字符串中第一个匹配项的下标（实现strStr）
思路（暴力解法）
- 看到这题我们很容易想到，我们可以将字符串needle从头开始的每个字符逐一和字符串haystack的 字符逐一匹配（也是从第一个字符开始）
- 如果遇到不匹配的情况则继续从字符串haystack的第二个字符开始匹配，同理如果还是遇到不匹配的情况，则从第三个字符开始……以此类推，直至遍历完haystack或出现完全匹配的情况
- 若出现了完全匹配的情况，则返回第一个匹配项的下标，如示例一。
具体步骤
- 首先计算字符串haystack和字符串needle的长度
int len_hay = strlen(haystack); int len_need = strlen(needle); //如果needle的长度大于haystack的，那么不可能出现完全匹配的情况，直接返回-1 if(len_need > len_hay) return -1;
- 接着就开始将字符串needle和字符串haystack开始匹配，直至遍历完字符串haystack
实现代码
int strStr(char * haystack, char * needle){ int len_hay = strlen(haystack); int len_need = strlen(needle); if(len_need > len_hay) return -1; int i = 0,j = 0; int count_j = 0; while(1) { i = 0; //每一次都要从字符串needle第一个字符开始匹配 j = count_j; if(haystack[j] == '\0') //如果if条件为真，就说明haystack已经遍历完，且没有出现完全匹配的情况，返回-1 return -1; //将字符串needle和字符串haystack的字符逐一匹配 while(needle[i] == haystack[j] && needle[i] != '\0' && haystack[j]!= '\0') { i++; j++; } //如果循环退出后needle[i]为'\0'，就说明已经完全匹配，返回第一个匹配项的下标 if(needle[i] == '\0') return count_j; //如果未完全匹配，则从haystack的下一个字符开始重新与字符串needle进行匹配 else count_j++; } return -1; }
tips：这道题如果用暴力解法，其时间复杂度为O(M * N),其实正确的解法应该是KMP算法，这样可以将时间复杂度降为O(N)，但由于KMP算法较难理解，笔者还未完全悟透，故以后再和大家分享KMP算法，和本题如何用KMP算法求解。
