神华科技 网站建设,360免费建站怎么做,页面设计理念怎么写,ps 矢量素材网站文章目录重点1. 简单模式匹配算法2. 部分匹配值PM的算法#xff08;Move j-1 PM[j-1]#xff09;3. 部分匹配值PM的两次改进#xff08;Move j-next[j]#xff09;4. 快速得到next数组5. KMP匹配算法重点
童鞋们看网上讲解的时候一定要分清楚序列是从0开始还是从1开始Move j-1 PM[j-1]3. 部分匹配值PM的两次改进Move j-next[j]4. 快速得到next数组5. KMP匹配算法重点
童鞋们看网上讲解的时候一定要分清楚序列是从0开始还是从1开始有些博主就是纯纯的转载文章没有任何修改把一篇错误的文章转来转去误导了同学们。
所以我在这里提醒同学们一定要注意序列下标从什么开始的。
我的算法是根据王道考研总结出来的并且主串、模式、next的下标都是从1开始的
1. 简单模式匹配算法 int search(String txt, String part){for(int i0; itxt.length-part.length; i){for(int j0; jM; j){if(part[j] ! txt[ij]) break;}if(j M) return i;}return -1;
}2. 部分匹配值PM的算法Move j-1 PM[j-1]
1. 部分匹配值PM 模式a b c a c ‘a’的前缀为空后缀为空两者交集为空 ‘ab’的前缀为{a}后缀为{b}两者交集为空 ‘abc’的前缀为{a,ab}后缀为{bc,c},两者交集为空 abca’的前缀为{a,ab,abc}后缀{bca,ca,a}两者交集为{a} ‘abcac’的前缀为{a,ab,abc,abca}后缀{bcac,cac,ac,c}两者交集为空 2. 利用上述得到的部分匹配值PM完成匹配 【第一趟匹配过程】 发现a与c不匹配前两个字符是匹配的查表可知最后一个匹配字符b对应的部分匹配值为0因此移动位数已匹配的字符数 - 对应的部分匹配值2-02所以将子串向后移动2位。j1PM 【第二趟匹配过程】 发现b与c不匹配前四个字符是匹配的查表可知最后一个匹配字符a对应的部分匹配值为1因此移动位数已匹配的字符数 - 对应的部分匹配值4-13所以将子串向后移动3位。j1PM 【第三趟匹配过程】 成功 3. 具体实例
3. 部分匹配值PM的两次改进Move j-next[j]
已知右移位数已匹配的字符数 - 对应的部分匹配值即为Movej-1- PM[j-1]
使用部分匹配值时每当匹配失败就去找它前一个元素的部分匹配值这样使用起来有些不方便所以将PM表右移一位这样哪个元素匹配失败直接看它自己的部分匹配值即可。 有时候为了让公式变得更加简洁可以将next数组整体1 于是next数组就出来了
4. 快速得到next数组
1. 手动画图 已知串 S babab , 求 Next 数值序列模式匹配 首先第一位0第二位1。这个是固定的。第三位字符串是“bab”这时候“bab”的前缀有bba后缀有abb可以看出前后缀相等的最长的字符串只有b因为b的长度是1所以这里第三位的next值就是1。第四位字符串是“baba”前缀是b,ba,bab后缀是aba,ba,a。这里可以看出前后缀相等的最长的字符串是ba长度是2因此第四位的next值是2。第五位字符串是“babab”前缀是b,ba,bab,baba后缀是abab,bab,ab,b。这里可以看出前后缀相等的最长的字符串是bab长度是3因此第五位的next值是3.因此综合起来next值就是0 1 1 2 3 2. 代码实现next数组
void get_next(String T,int next[]){int i1,j0;next[1]0;while(iT.length){if(j0||T.ch[i]T.ch[j]){i,j;next[i]j;}else jnext[j];}
}5. KMP匹配算法
int Index(SString S,SString T,int next[]){int i1,j1;while(iS.lengthjT.length){//相同的话就一直匹配 if(j0||S.ch[i]T.ch[j]){ i; j; }//不同的话就回溯else{ jnext[j];}}//找到了(i-1)-(T.length-1)i-T.lengthifjT.length return i-T.length; //没找到else return 0;
}
