菜鸟学C第13题:编写函数IND，让它判断一个字符串是否为另一个字符串的子串的功能：
https://www.52pojie.cn/forum.php ... d=665350&page=1
[Asm] 纯文本查看 复制代码
源于我的上一个学习贴
菜鸟学C第13题:编写函数IND，让它判断一个字符串是否为另一个字符串的子串的功能：
[url]https://www.52pojie.cn/forum.php?mod=viewthread&tid=665350&page=1[/url]
有一个朋友给我说我的方法太low，让我看看KMP算法，我就去看了一下。
我自己根据KMP的思想写了一个，但是我在网上看见一个更好的更精彩的方法。如果真的能徒手写出这样的代码，功力之深厚，让我武侠小说里的绝世高手
发出来交流一下，我没时间再深入下去了，毕竟我还是一个嫩鸟。
//2017年11月20日17:02:42 自己根据kmp算法思想实现的字符串匹配，效率非常的低
void next(int * arr, char * str, int length) {
for (int i = 0; i < length - 1; i++) {
int max = 0;
for (int j = i-1; j >= 0; j--) {
int num = 0;
int flag = 1;
while (num <=j) {
if (str[num] != str[i- j+num]) {
flag = 0;
break;
}
num++;
}
if (flag) {
max = j+1;
break;
}
}
arr[i] = max;
}
}
void mainff() {
char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";
int arr[7] = { 0 };
next(arr, ptr, 7);
/*for (int i = 0; i < 7; i++) {
printf("%d\n", arr[i]);
}*/
int length1 = strlen(str);
int length2 = strlen(ptr);
for (int i = 0; i < length1; i++) {
int flag = 1;
for (int j = 0,num=0; j < length2; j++,num++) {
if (str[i + j] != ptr[j] || str[i + j] == '\0') {
flag = 0;
if ( num &&arr[num - 1]) {
i = i + num - arr[num - 1];
}
break;
}
}
if (flag) {
printf("找到!,%d",i);
}
}
/*for (int i = 0; i < 7; i++) {
printf("%d\n", arr[i]);
}*/
//printf("%d", IND("12ab5","abc"));
getchar();
}
//根据网上实现
//求从1到str长度-1的每一个子串的最长的相同的前缀。
void newnext(int * arr, char * str, int length) {
//思路：考虑 字符串abcabcd 思路是从第二个位置b开始，一路找，找到第一个a存在的位置，在这之前都不会有最长的相同的前缀个数。找到后，判断第二个字符b是否等于 找到第一个a的后面的字符。相等，最长的相同的前缀就一定会加1.当不相等就会回溯
int k = -1;
arr[0] = -1;
for (int i = 1; i < length - 1; i++) {
while (k > -1 && str[k + 1] != str[i]) {
k = arr[k]; //回溯。考虑字符串 cfgdcfXcfgdcfg，cfgdcf,cfgdcf相同，进一步的X不等于g，这是需要考虑cfgdcf最长的相同的前缀的个数。即为cf所以k=1，后判断str[k+1]==str[i]，所以k++；
} //很简单的 考虑另一个字符串abcdeXabcdeg ，在X!=g之后，考虑abcde这个字符串的最长的相同的前缀，说明什么，a开头的没有其他的数能够出现在g的前方，而在上方，cfgdcf虽然后面的X不等于g，但是其回溯后的cf任然是等于前方g的cf，这个时候又判断后方是否相同。
if (str[k + 1] == str[i]) {
k = k + 1;
}
arr[i] = k;
}
}
int KMP(int * arr, char * str,char*substr,int length) {
int k = -1;
newnext(arr, substr, length);
for (int i = 0; i < strlen(str); i++) {
while (k > -1 && substr[k + 1] != str[i]) {
//母串在不停的往前奏，但是子串却会回溯。
// ababd ddddd
// ababe 考虑这两个字符串，当d!=e时，k会判断abab的最长的相同的前缀为ab，这时只需要将d与子串ab后面的a判断
k = arr[k];
}
if (substr[k + 1] == str[i]) {
k++;
}
if (k == strlen(substr)-1) {
return i - strlen(substr)+1;
}
}
return 0;
}
void main() {
char *str = "bacbababadababacambabacaddababacasdsd";
char *substr = "ababaca";
int arr[7];
printf("%d",KMP(arr, str, substr, 7));
getchar();
}
参考：http://blog.csdn.net/starstar1992/article/details/54913261
参考：百度百科 | 
发表于 2017-11-20 18:59
