字符串模式匹配之KMP改进算法

串是字符串的简称，是计算机中常见且重要的数据结构。串 (string)是由零个或多个字符组成的有限连续序列。串中字符的个数称为串的长度，含有零个元素的串叫空串。空格串不是空串，而是由一个或多个空格组成的串。空格串也是字符集合的一个元素。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象。在串的基本操作中，通常以“串的整体”作为操作对象。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。设S和T是两个给定的串，在主串S中找等于T的子串的过程称为模式匹配。

⑴模式匹配中最关键的是如何求模式串的next数组，然后对next数组修正为nextval数组，如下图：

⑵KMP改进的算法

/*int KMPNextval( Str substr, int nextval[ ] )

{

int j=0,i = 1;
nextval[1]=0
while( i < substr.length)
{
if( j==0 || substr.ch[i] == substr.ch[j])
{
++i;
++j;
if(substr.ch[i]!= substr.ch[j] )
{
nextval[i] = j;
}
else
{
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j];
}
}

}
*/

⑶模式匹配的应用

①搜索引擎的关键字检索

②各类文本编辑器的“查找”功能

③其它技术领域