思路：一个个匹配，如原始数据A为“abcdefg”，匹配数据B为“de”，将B[0]和A[0]比较，不同则比较B[0]和A[1]，依次类推，直到B[0]和A[3]相同，则比较B[1]和A[4]，以此类推；
缺点：效率低
实现代码：
#include2、KMP算法#include #define MAXLEN 255 typedef struct { char data[MAXLEN]; int len; }String; int Index_BF( String S, String T ) { int i, j, k; int s_Len = S.len, t_Len = T.len; for( i = 0; i < s_Len-t_Len; i++ ) { j = 0; k = i; while( j < t_Len && S.data[k] == T.data[j] ) { j++; k++; } if( j == t_Len) { return i; } } return -1; } int main(void){ String S, T; memcpy(S.data, "sasdfXGHadsad", 13); memcpy(T.data, "ad", 2); printf("%d", Index_BF(S,T)); }
实现思路：
名词说明：下面说的
“主串”——代表的是被搜索的字符串；
“模式串”——代表的是匹配的字符串；
首先我们需要引入一个next数组，用于存储模式串每个元素的前后缀的最大公共元素数量，也可以理解为该元素失配时所需要回溯到模式串的哪个位置，怎么理解这句话呢？
如，现有一个模式串modelStr的值“abaabcac”，该模式串所对应的next函数值如下表所示：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| T | a | b | a | a | b | c | a | c |
| next[] | -1 | 0 | 0 | 1 | 1 | 2 | 0 | 1 |
怎么得到这个表呢？
首先理解下前后缀的最大公共元素数量：
- 前后缀不包括本身，前缀从第一个字符开始看，后缀从最后一个字符开始看，如果第一个字符和最后一个字符都不相同那就不用再看了，next值直接为0，如果相同则前缀往由看，后缀往左看；
- 如一个字符串为“abcd”，那么c前面的字符串为"ab"，前缀是a，后缀是b，前缀和后缀不相同，则前后缀的最大公共元素数量为0；d前面的字符串为"abc"，前缀是a，后缀是c，前缀和后缀不相同，则前后缀的最大公共元素数量也为0；
- 如一个字符串为“aaaa”，那么第4个a的字符串为"aaa"，最大前缀是aa，最大后缀是aa，前缀和后缀存在相同元素，最大相同元素字符数为2，则前后缀的最大公共元素数量为2；
重新回头去看函数表
- 首先next[]数组的第0个索引固定为-1，-1的意思是说主串的当前位置和模式串的第一个元素匹配，所以a对应next[0]的值就是-1；
- b的前缀元素是a，前后缀的最大公共元素数量是0，所以a对应next[0]的值就是0，也就是说当匹配到b且失配的时候，应该读取next[1]的值为0，那么下个匹配的值就应该是modelStr[0]所存储的数值——a;
- modelStr[2]的值是a，前面字符串是“ab”，前缀是a，后缀是b，前后缀的最大公共元素数量是0；
- modelStr[3]的值是a，前面字符串是“aba”，前缀是a，后缀是a，前后缀的最大公共元素是a，前后缀的最大公共元素数量是1；
- modelStr[4]的值是b，前面字符串是“abaa”，前缀是a，后缀是a，前后缀的最大公共元素是a，前后缀的最大公共元素数量是1；
- modelStr[5]的值是c，前面字符串是“abaab”，前缀是ab，后缀是ab，前后缀的最大公共元素是a，前后缀的最大公共元素数量是2；
- modelStr[6]的值是a，前面字符串是“abaabc”，前缀是a，后缀是c，前后缀的最大公共元素是a，前后缀的最大公共元素数量是0；
- modelStr[7]的值是c，前面字符串是“abaabca”，前缀是a，ab，后缀是ba，a，前后缀的最大公共元素是a，前后缀的最大公共元素数量是1；
那么为什么要这么标记呢？
next数组所标记的数值是前后缀的最大公共元素数量，也相当于前缀和后缀之间第一个失配的元素的索引，比如模式串“abaabcac”，元素c的值next值为2，对应的模式串[2]的元素为a，那么下次就直接在拿第2个a开始匹配。
因为在c处失配了，那么说明前面的"abaab"都形同，那么c失配，主串的前面就一定是abaab，又因为我们前面已经知道模式串的最大公共前后缀元素数量为2，所以我们就可以直接拿模式串元素索引值为2的元素a去匹配c失配的元素，那么ab就对齐了，如下表所示
实现代码：
#include#include #define MAXLEN 100 typedef struct { char data[MAXLEN]; int len; }String; void GetNext( String T, int* next ) { int j = 0, k = -1; next[0] = -1; while( j < T.len-1 ) { if( k == -1 || T.data[j] == T.data[k] ) { k++; j++; next[j] = k; } else { k = next[k]; } } } int Index_KMP( String S, String T ) { int next[MAXLEN]; int i = 0, j = 0, k = 0, v = 0; GetNext(T, next); printf("next数组:"); for( k = 0; k < T.len; k++ ) { printf("%d", next[k]); } printf("rn"); while( i < S.len && j < T.len ) { if( j == -1 || S.data[i] == T.data[j] ) { i++; j++; } else { j = next[j]; } } if( j >= T.len ) { v = i - T.len; } else { v = -1; } return v; } int main( void ) { String S, T; printf("请输入主串S："); gets(S.data); S.len = strlen(S.data); printf("请输入模式串T："); gets(T.data); T.len = strlen(T.data); printf("串S：%srn", S.data); printf("串T：%srn", T.data); printf("T在S中的位置:%d", Index_KMP(S, T) ); }
Leetcode题目28：
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2
示例 2：
输入：haystack = “aaaaa”, needle = “bba”
输出：-1
实现程序：
void GetNext( char * needle, int* next, int needle_Len)
{
int j = 0, k = -1;
next[0] = -1;
while( j < needle_Len-1 ) {
if( k == -1 || needle[j] == needle[k] ) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
}
int strStr(char * haystack, char * needle){
int* next = NULL;
int haystack_Len = 0, needle_Len = 0;
int i = 0, j = 0, k = 0, v = 0;
haystack_Len = strlen(haystack);
needle_Len = strlen(needle);
next = (int*) malloc (sizeof(int)*needle_Len);
GetNext(needle, next, needle_Len);
while( i < haystack_Len && j < needle_Len ) {
if( j == -1 || haystack[i] == needle[j] ) {
i++;
j++;
} else {
j = next[j];
}
}
if( j >= needle_Len ) {
v = i - needle_Len;
} else {
v = -1;
}
free(next);
return v;
}
