一、串的定长顺序存储
#define MAXLEN 255
typedef struct
{
char ch[MAXLEN];
int length;
}SString;
二、朴素模式匹配算法 O(mn)
int Index(SString S,SString T)
{
int i = 1,j = 1;
while(i <= S.length && j <= T.length)
{
if(S.ch[i] == T.ch[j]) //匹配，继续比较
++i,++j;
else
{
i = i - j + 2; //主串指针回退到子串的第二个字符
j = 1;//模式串指针回退到第一个字符
}
}
if(j > T.length) return i - T.length;//无需加1，因为i自身在下一个位置
else return 0;
}
三、KMP匹配算法 O(n)
匹配算法
int Index_KMP(SString S,SString T,int next[])
{
int i = 1,j = 1;
while(i <= S.length && j <= T.length)
{
if(j == 0 || S.ch[i] == T.ch[j])
++i,++j;
else
j = next[j]; //模式串向右移动
}
if(j > T.length) return i - T.length;
else return 0;
}
next数组推导算法
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while(i < T.length)
{
if(j == 0 || T.ch[i] == T.ch[j])
{
i++,j++;
next[i] = j;//next[j+1] = next[j] + 1
}
else j = next[j];
}
}