這篇文章主要介紹了KMP算法有什么用,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù),包含不限于做網(wǎng)站、網(wǎng)站建設(shè)、大城網(wǎng)絡(luò)推廣、微信小程序定制開發(fā)、大城網(wǎng)絡(luò)營銷、大城企業(yè)策劃、大城品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等,從售前售中售后,我們都將竭誠為您服務(wù),您的肯定,是我們最大的嘉獎;創(chuàng)新互聯(lián)建站為所有大學生創(chuàng)業(yè)者提供大城建站搭建服務(wù),24小時服務(wù)熱線:13518219792,官方網(wǎng)址:bm7419.com
KMP算法實例詳解
KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其對于任何模式和目標序列,都可以在線性時間內(nèi)完成匹配查找,而不會發(fā)生退化,是一個非常優(yōu)秀的模式匹配算法。
分析:KMP模板題、KMP的關(guān)鍵是求出next的值、先預(yù)處理出next的值、然后一遍掃過、復(fù)雜度O(m+n)
實例代碼:
#include<stdio.h> #include<string.h> #define N 1000005 int s[N]; int p[N]; int next[N]; int m,n; void getnext(){ int j=0,k=-1; next[0]=-1; while(j<m){ if(k==-1||p[j]==p[k]){ j++; k++; next[j]=k; } else k=next[k]; } } int kmp(){ int i=0,j=0; getnext(); while(i<n){ if(j==-1||s[i]==p[j]){ i++; j++; } else j=next[j]; if(j==m) return i; } return -1; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&s[i]); for(int i=0;i<m;i++) scanf("%d",&p[i]); if(kmp()==-1) printf("-1\n"); else printf("%d\n",kmp()-m+1); } return 0; }
感謝你能夠認真閱讀完這篇文章,希望小編分享的“KMP算法有什么用”這篇文章對大家有幫助,同時也希望大家多多支持創(chuàng)新互聯(lián),關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道,更多相關(guān)知識等著你來學習!
當前題目:KMP算法有什么用
本文鏈接:http://bm7419.com/article24/pciice.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供品牌網(wǎng)站建設(shè)、標簽優(yōu)化、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、微信公眾號、企業(yè)網(wǎng)站制作
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)