ASP.net基于内容的音乐检索方法研究(9)
算法描述[9]：
当模式匹配执行到比较字符Ti和Pi，其中l=i=n，l=j=m。
(1)若Ti=Pj则继续往右作匹配检测，即对Ti+1和Pj+l；进行匹配检测。
(2)若Ti≠Pj时则分两种情况进行讨论：
第一种情况：若j=l，则对Ti+l和Pi进行匹配检测，即把模式和正文向右移动一位再从模式的第一个字符进行匹配。
第二种情况：若l<j=m，们将试图在模式中找到一个合适位置再进行比较，们把这个下标记做next[j]。执行Ti和next[j]的匹配，其中next[j]的构造是算法的核心，约定如下：
Next[j]=-1,当j=0时
Next[j]=max｛k|0<k<j且“P0 P1…Pk-1”=“Pj-k Pj-k+1…Pj-1”｝此集合不为空集
Next[j]=0，其他情况
由于本文主讲的是KMP算法，估计们举例详细说明，如主串为ababcabcacbab，模式串为abcac，匹配过程如下图3-2:
上一篇：云计算在校园网中的应用与研究