#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxSize 256
typedef struct string{
char str[MaxSize];
int length, maxLength;
}String;
//从模式串p_start位置与主串s_start位置开始进行匹配
int Match(String s, String p, int s_start, int p_start, int *s_fail, int *p_fail)
{
int i = s_start, j = p_start;
p.length=strlen(p.str);
for (; j < p.length; i++, j++)
{
if (s.str[i] != p.str[j])
{
*s_fail = i; //s_fail记录主串失配位置
*p_fail = j; //p_fail记录模式串失配位置
return 0;
}
}
return 1;
}
//简单匹配算法 主串：s 模式串：p 开始查找的位置：pos
int Index(String s, String p, int pos)
{
int s_start, p_start = 0, s_fail, p_fail;
s.length=strlen(s.str);
p.length=strlen(p.str);
for (s_start = pos; s_start <= s.length - p.length; s_start++)
{
if (Match(s, p, s_start, p_start, &s_fail, &p_fail))
{
printf("简单匹配算法在主串%d的位置匹配成功！\n", s_start);
return s_start;
}
}
return 0;
}
//失败函数
void Fail(String p, int *fail)
{
int j = 0, k = -1;
fail[0] = -1;
p.length=strlen(p.str);
while (j < p.length)
{
if (k == -1 || p.str[j] == p.str[k]) //如果是第一个字符或遇到相同的字符
{
j++;
k++;
fail[j] = k;
}
else
k = fail[k];
}
}
//KMP算法
int KMPIndex(String s, String p, int pos, int *fail)
{
int s_start = 0, p_start = 0, s_fail, p_fail;
s.length=strlen(s.str);
p.length=strlen(p.str);
while (s_start <= s.length - p.length)
{
if (Match(s, p, s_start, p_start, &s_fail, &p_fail))
{
printf("KMP算法匹配成功在%d的位置匹配成功\n",s_start);
return s_start;
}
else{ //本趟匹配失败时，根据失败函数计算下一趟主串与模式串的开始匹配位置
p_start = fail[p_fail];
s_start = s_fail;
if (p_start == -1){ //在模式串第一个字符上发生失配的特殊情况
p_start = 0;
s_start++;
}
}
}
return -1;
}
int main(){
String S, P;
printf("请输入主串S：");
scanf("%s", S.str);
printf("请输入模式串（子串）P：");
scanf("%s", P.str);
printf("主串：%s\n", S.str);
printf("模式串：%s\n", P.str);
int a=Index(S, P, 0);
if(!a)
printf("简单匹配算法失败！未能找到模式串。");
int *fail=new int[100];
Fail(P,fail);
int b=KMPIndex(S,P,0,fail);
if(!b)
printf("KMP匹配算法失败！未能找到模式串。");
}
网友评论