1 求子串位置的定位函数Index(S,T,pos)
     子串的定位操作通常称作串的模式匹配(其中T被称为模式串),是各种串处理系统中最
重要的操作之一。在以前借用串的其他基本操作给出了定位函数的一种算法。根据以前算法
的基本思想,采用定长顺序存储结构,可以写出不依赖于其他串操作的匹配算法,如算法1所
示。
int Index(Sstring S, Sstring T,int pos){
  //返回子串T在主串s中第pos个字符之后的位置。若不存在,则函数值为0。
  //其中,T非空,1≤Pos≤StrLength(S)。
      i=pos；   
j=1；
      while(i<=S[0]&&j<=T[0]) {
      if(s[i]==T[j]) { i++; j++; }   //继续比较后继字符      ·
      else { i=i-j+2； j=1；}          //指针后退重新开始匹配
      }
      if(i>T[0]) return i-T[0]；
      else return 0；
} //Index
      算法   1

     在算法1的函数过程中,分别利用计数指针i和j指示主串S和模式串T中当前正待比较
的字符位置。算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较之,
若相等,则继续逐个比较后续字符,否则从主串的下一个字符起再重新和模式的字符比较之。
依次类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则称匹配成
功,函数值为和模式T中第一个字符相等的字符在主串S中的序号,否则称匹配不成功,函数值
为零。图1展示了模式T="abcac"和主串S的匹配过程(pos=1)。
算法1的匹配过程易於理解,且在某些应用场合,如文本编辑等,效率也较高,例如,在检查模式
"STING"是否存在於下列主串中时,     
"A STRING SEARCHING EXAMPLE CONSISTING OF SIMPLE TEXT"
上述算法中的WHILE循环次数(即进行单个字符比较的次数)为41,恰好为
(Index+T[0]-1)+4这就是说，除了主串中呈黑体的四个字符，每个字符比较了两次以外，其
它字符均只和模式进行一次比较。在这种情况下，此算法的时间复杂度为O(n+m)。其中n
和m分别为主串和模式的长度。然而，在有些情况下，该算法的效率却很低。例如，当模
式串为"00000001"，而主串为
"00000000000000000000000000000000000000000000000000001"时，由于模式中前7个字符
均为"0"，又，主串中前52个字符均为"0"，每趟比较都在模式的最后一个字符出现不等，
此时需将指针i回溯到i-6的位置上，并从模式的第一个字符开始重新比较，整个匹配过程
中指针i需回溯45次，则WHILE循环次数为46* 9(index*m)。可见，算法1在最坏情况下
的时间复杂度为O(n*m)。这种情况在只有0、1两种字符的文本串处理中经常出现，因为在
主串中可能存在多个和模式串“部分匹配”的子串，因而引起指针i的多次回溯。01串可以
用在许多应用之中。比如，一些计算机的图形显示就是把画面表示为一个01串，一页书就
是一个几百万个0和1组成的串。在二进位计算机上实际处理的都是01串。一个字符的ASCII
码也可以看成是八个二进位的01串。包括汉字存储在计算机中处理
时也是作为一个01串和其它的字符串一样看待。因此在下一节，我们将介绍另一种较好的
字符串长度17模式串长度8模式匹配算法。
2   模式匹配的一种改进算法
这种改进算法是D．E．Knuth与V．R．Pratt和J．H．Morris同时发现的，因此人们称它
为克努特-莫里斯-普拉特操作(简称为KMP算法)。此算法可以在O(n+m)的时间数量级上完
成串的模式匹配操作。其改进在於: 每当一趟匹配过程中出现字符比较不等时，不需回溯i
指针，而是利续进行比较。下面先从具体例子看起。
回顾图1中的匹配过程示例，在第三趟的匹配中，当i=7,j=5字符比较不等时，又从i=4，
j=1重新开始比较。然后，经仔细观察可发现，在i=4和j=1;i=5和j=1以及i=6和j=1这三
次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中第4、5和6个字
符必然是‘b’、‘c’和‘a’(即模式串中第2、3和4个字符)。因为模式中的第一个字符是
a，因此它无需再和这三个字符进行比较，而仅需将模式向右滑动三个字符的位置继续进行
i=7、j=2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式向右移动
二个字符的位置继续进行i=3、j=1时的字符比较。由此，在整个匹配的过程中，i指针没有
回溯。
     现在讨论一般情况。假设主串为]，模式串为]，从上例的分析可知，为了实
现改进算法，需要解决下述问题：当匹配过程中产生“失配”(即s[i]!=p[j])时，模式串“向
右滑动’’可行的距离多远，换句话说，当主串中第i个字符与模式中第j个字符“失配’’
(即比较不等)时，主串中第i字符(i指针不回溯)应与模式中哪个字符再比较?
假设此时应与模式中第k(k<j)个字符继续比较，则模式中前k-1个字符的子串必须满足下列
关系式，且不可能存在kk>k满足下列关系式而已经得到的“部分匹配”的结果推得下列等
式
p[1..k-1]==s[i-k+1..i-1]
而已经得到的部分结果是
p[j-k+1..j-1]==s[i-k+1..i-1]
推得以下结果
p[1..k-1]==p[j-k+1..j-1]
反之，若模式串中存在满足式的两个子串，则当匹配过程中，主串中第i个字符与模式中第
j个字符比较不等时，仅需将模式向右滑动至模式中第是个字符和主串中第i个字符对齐，
此时，模式中头是k-1个字符的子串p[1..k-1]必定与主串中第i个字符之前长度为k-1的子
串s[i-k+1..i-1]相等，由此，匹配仅需从模式中第i个字符与主串中第j个字符比较起继续进
行。
     若令next[j]=k，则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模
式中需重新和主串中该字符进行比较的字符的位置。由此可引出模式串的next函数的定义：
      next[j]=0      当j=1时
      next[j]=Max{k|1<k<j && p[1..k-1]==p[j-k+1..j-1] 当此集合不空时
      next[j]=1 其它情况
由此定义可推出下列模式串的next函数值：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。