初始条件：
串S和T存在，T是非空串，假如S为：a b a b c
a b c a c b a b T为：a b c a c
1≤pos≤StrLength(S)。
操作结果：若主串S中存在和串T值相同的子串,
则返回它在主串S中第pos个字符之后
第一次出现的位置;
否则函数值为0。
...................................................
/ 返回子串T在主串S中第pos个字符之后的位置。
// 若不存在，则函数值为0。
// 其中，T非空，1≤pos≤StrLength(S)。
{
i=pos;
while(i<=s[0] && j<=T[0])
{
if(s[i]==T[j]) / /继续比较后继字符
{
++i;++j;
}
else //指针后退重新开始匹配
{
i=i-j+2;
}
}
if(j>T[0])
{
return i-T[o];
}
else //若不存在则返回 0
{
return 0;
}
}
2.首尾匹配算法
先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。
SString T,
int pos)
{
// 返回子串T在主串S中第pos个字符之后的位置。
// 若不存在，则函数值为0。
// 其中，T非空，1≤pos≤StrLength(S)。
sLength
= S[0];
tLength =
T[0];
i =
pos;
patStartChar
= T[1];
patEndChar
= T[tLength];
while (i
<= sLength
– tLength
+ 1)
{
if (S[i]
!= patStartChar)
++i;
//重新查找匹配起始点
else if (S[i+tLength-1]
!= patEndChar)
++i;
// 模式串的“尾字符”不匹配
else // 检查中间字符的匹配情况
{
k
= 1; j
= 2;
while ( j
< tLength
&& S[i+k]
= T[j] )
{
++k;
++j;
}
if ( j
== tLength )
return i;
else
++i;
// 重新开始下一次的匹配检测
}
}
return 0;
}
SString T,
int pos)
// 利用模式串T的next函数求T在主串S中第pos个
// 字符之后的位置的KMP算法。其中，T非空，
// 1≤pos≤StrLength(S)
i =
pos; 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;
} // Index_KMP