KMP 算法實(shí)例詳解

更新時(shí)間：2017年07月27日 10:47:56 投稿：lqh

這篇文章主要介紹了KMP 算法實(shí)例詳解的相關(guān)資料,MP的關(guān)鍵是求出next的值、先預(yù)處理出next的值，需要的朋友可以參考下

KMP 算法實(shí)例詳解

KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其對于任何模式和目標(biāo)序列，都可以在線性時(shí)間內(nèi)完成匹配查找，而不會發(fā)生退化，是一個(gè)非常優(yōu)秀的模式匹配算法。

分析：KMP模板題、KMP的關(guān)鍵是求出next的值、先預(yù)處理出next的值、然后一遍掃過、復(fù)雜度O（m+n）

實(shí)例代碼：

#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 算法的實(shí)例詳解本站關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的文章還有很多，希望大家搜索查閱，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章:

KMP
算法

相關(guān)文章

C語言設(shè)計(jì)一個(gè)閃閃的圣誕樹
本文使用C語言基礎(chǔ)知識在控制臺打印一個(gè)圣誕樹效果，真的很簡單哦，一起通過本文學(xué)習(xí)吧
2016-12-12
VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法
這篇文章主要介紹了VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法,對于理解windows程序運(yùn)行原理的進(jìn)程問題有一定的幫助,需要的朋友可以參考下
2014-07-07
C/C++實(shí)現(xiàn)監(jiān)控目錄文件變化
ReadDirectoryChangesW是Windows操作系統(tǒng)提供的一個(gè)函數(shù),用于監(jiān)視目錄的變化,本文主要為大家介紹了如何使用ReadDirectoryChangesW實(shí)現(xiàn)監(jiān)控目錄文件變化,需要的可以參考下
2023-11-11
linux c模擬ls命令詳解
本篇文章是對linux中基于c模擬ls命令的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-06-06
Qt實(shí)現(xiàn)可以計(jì)算大數(shù)的簡單計(jì)算器
計(jì)算器是我們生活中很常見的東西，它可以由多種語言多種方式來實(shí)現(xiàn)。本文主要介紹的是基于C++語言，由QT實(shí)現(xiàn)的可以計(jì)算大數(shù)的簡單計(jì)算器，需要的可以參考一下
2022-12-12
C語言實(shí)現(xiàn)簡單酒店管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單酒店管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-03-03
C++ Boost Heap使用實(shí)例詳解
Boost是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱。Boost庫是一個(gè)可移植、提供源代碼的C++庫，作為標(biāo)準(zhǔn)庫的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語言標(biāo)準(zhǔn)庫提供擴(kuò)展的一些C++程序庫的總稱
2022-11-11
C語言之素?cái)?shù)(質(zhì)數(shù))的判斷以及輸出
這篇文章主要介紹了C語言之素?cái)?shù)(質(zhì)數(shù))的判斷以及輸出方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2023-03-03
C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解
單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。本文將為大家詳細(xì)講講單向鏈表的實(shí)現(xiàn)與使用，需要的可以參考一下
2022-08-08
C++詳細(xì)分析講解函數(shù)參數(shù)的擴(kuò)展
在C++中，定義函數(shù)時(shí)可以給形參指定一個(gè)默認(rèn)的值，這樣調(diào)用函數(shù)時(shí)如果沒有給這個(gè)形參賦值（沒有對應(yīng)的實(shí)參），那么就使用這個(gè)默認(rèn)的值。也就是說，調(diào)用函數(shù)時(shí)可以省略有默認(rèn)值的參數(shù)
2022-04-04