建设网站制作汉狮团队,海口专业网站制作策划,无锡大型网站建设公司,黑白高端大气网站设计工作室织梦dedecms模板kmp算法完成的任务是#xff1a;给定两个字符串O和f#xff0c;长度分别为n和m#xff0c;判断f是否在O中出现#xff0c;如果出现则返回出现的位置。常规方法是遍历a的每一个位置#xff0c;然后从该位置开始和b进行匹配#xff0c;但是这种方法的复杂度是O(nm)。kmp算法…kmp算法完成的任务是给定两个字符串O和f长度分别为n和m判断f是否在O中出现如果出现则返回出现的位置。常规方法是遍历a的每一个位置然后从该位置开始和b进行匹配但是这种方法的复杂度是O(nm)。kmp算法通过一个O(m)的预处理使匹配的复杂度降为O(nm)。
参考链接【经典算法】——KMP深入讲解next数组的求解 - c_cloud - 博客园 讲解的非常清楚明白
主要就是next数组的求解
KMP算法的核心所在就是next数组的求解不过在这里我找到了一个全新的理解方法如果你懂的上面我写的的那么下面的内容你只需稍微思考一下就行了
跟刚才一样我用一句话来阐述一下next数组的求解方法其实也就是两个字
继承
a、当前面字符的前一个字符的对称程度为0的时候只要将当前字符与子串第一个字符进行比较。这个很好理解啊前面都是0说明都不对称了如果多加了一个字符要对称的话最多是当前的和第一个对称。比如agcta这个里面t的是0那么后面的a的对称程度只需要看它是不是等于第一个字符a了。
b、按照这个推理我们就可以总结一个规律不仅前面是0呀如果前面一个字符的next值是1那么我们就把当前字符与子串第二个字符进行比较因为前面的是1说明前面的字符已经和第一个相等了如果这个又与第二个相等了说明对称程度就是2了。有两个字符对称了。比如上面agctag倒数第二个a的next是1说明它和第一个a对称了接着我们就把最后一个g与第二个g比较又相等自然对称成都就累加了就是2了。
c、按照上面的推理如果一直相等就一直累加可以一直推啊推到这里应该一点难度都没有吧如果你觉得有难度说明我写的太失败了。
当然不可能会那么顺利让我们一直对称下去如果遇到下一个不相等了那么说明不能继承前面的对称性了这种情况只能说明没有那么多对称了但是不能说明一点对称性都没有所以遇到这种情况就要重新来考虑这个也是难点所在。 如果蓝色的部分相同则当前next数组的值为上一个next的值加一如果不相同就是我们下面要说的 如果不相同用一句话来说就是
从前面来找子前后缀
1、如果要存在对称性那么对称程度肯定比前面这个的对称程度小所以要找个更小的对称这个不用解释了吧如果大那么就继承前面的对称性了。
2、要找更小的对称必然在对称内部还存在子对称而且这个必须紧接着在子对称之后。
如果看不懂那么看一下图吧 说了这么多下面是代码实现
#include stdio.h
#include stdlib.h
#include string.h
#define N 100void cal_next( char * str, int * next, int len )
{int i, j;next[0] -1;for( i 1; i len; i ){j next[ i - 1 ];while( str[ j 1 ] ! str[ i ] ( j 0 ) ){j next[ j ];}if( str[ i ] str[ j 1 ] ){next[ i ] j 1;}else{next[ i ] -1;}}
}int KMP( char * str, int slen, char * ptr, int plen, int * next )
{int s_i 0, p_i 0;while( s_i slen p_i plen ){if( str[ s_i ] ptr[ p_i ] ){s_i;p_i;}else{if( p_i 0 ){s_i;}else{p_i next[ p_i - 1 ] 1;}}}return ( p_i plen ) ? ( s_i - plen ) : -1;
}int main()
{char str[ N ] {0};char ptr[ N ] {0};int slen, plen;int next[ N ];while( scanf( %s%s, str, ptr ) ){slen strlen( str );plen strlen( ptr );cal_next( ptr, next, plen );printf( %d\n, KMP( str, slen, ptr, plen, next ) );}return 0;
}
参考链接 如果你看不懂KMP算法那就看一看这篇文章( 绝对原创绝对通俗易懂) - Stay Hungry,Stay Foolish - 博客频道 - CSDN.NET
字符串匹配算法总结 - WINCOL的专栏 - 博客频道 - CSDN.NET
