ASP.net基于内容的音乐检索方法研究(9)
时间:2017-04-13 10:38 来源:毕业论文 作者:毕业论文 点击:次
算法描述[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: (责任编辑：qin) |