一、算法设计思想
1.简单模式匹配算法
从主串的第一个位置开始和模式串的第一个字符开始比较,相等继续比较下一个字符;否则从主串的下一个字符和模式串的第一个字符重新开始比较,以此类推,直到比较完模式串的所有字符。匹配成功返回模式串在主串中的位置,否则返回0。
2.KMP
二、代码实现
1.
int Index(char str[],char substr[])
{
int i=1,j=1,k=i; //从1开始存储,k表示主串匹配开始位置,匹配失败自增1
while(i<=str[0]&&j<=substr[0]){
if(str[i]==substr[j]){
++i;
++j;
}
else{
j=1;
i=++k;
}
}
if(j>substr[0])
return k;
else
return 0;
}
2.KMP
//计算next数组(模式串的自我匹配)
void get_next(char T[],int next[])
{
int i=1,j=0; //串从下标1开始存储,0位置存储串长度
next[1]=0;
while(i<T[0]){
if(j==0||T[i]==T[j]){
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
//kmp匹配算法
int KMP(char S[],char T[],int next[])
{
int i=1,j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){
++i;
++j;
}
else
j=next[j];
}
if(j>T[0])
return i-T[0]; //匹配位置
else
return 0;
}