#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
//BF算法(一般思路的字符串匹配)
int BF(const char *s, const char *sub, int pos) //pos表示从s的pos位置处开始匹配
{
int i = pos;
int j = 0;
int lens = strlen(s);
int lensub = strlen(sub);
while ((i < lens) && (j < lensub))
{
if (s[i] == sub[j])
{
i++;
j++;
}
else
{
i = i - j + 1; //匹配失败，i回到开始匹配位置+1的下标处，j=0
j = 0;
}
}
if (j >= lensub)
{
return i - j;
}
else
{
return -1;
}
}
//KMP算法
void GetNext(int *next, const char *sub)
{
int lensub = strlen(sub);
next[0] = -1;
next[1] = 0;
int i = 2;
int k = 0;
while (i < lensub)
{
if ((k == -1) || (sub[i - 1] == sub[k]))
{
//next[i] = k + 1;
//i++;
//k += 1;
next[i++] = ++k;
}
else
{
k = next[k]; //不是k = next[i]，因为是在k位置处出现失配
}
}
//对next数组进行优化，当发生不匹配且next[j]元素与当前j下标元素相同，直接跳过，减少不必要的匹配
for (int j = 1; j < lensub; j++)
{
if (sub[next[j]] == sub[j])
{
next[j] = next[next[j]];
}
}
}
int KMP(const char *s, const char *sub, int pos)
{
int i = pos;
int j = 0;
int lens = strlen(s);
int lensub = strlen(sub);
int *next = (int*)malloc(lensub * sizeof(int));
assert(next != NULL);
GetNext(next, sub); //得到sub的next数组
while (i < lens && j < lensub)
{
if ((j == -1) || (s[i] == sub[j]))
{
i++;
j++;
}
else
{
j = next[j]; //匹配不相等时只改变j下标，i不用回退
}
}
free(next);
if (j >= lensub)
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
char *s = "abcabababcabd";
char *sub = "abcabd";
//int pos = BF(s, sub, 0);
int pos = KMP(s, sub, 0);
printf("%d\n", pos);
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-20736.html
