欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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)完成匹配查找，而不會(huì)發(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)和算法的文章還有很多，希望大家搜索查閱，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

相關(guān)文章

  • C++迭代器失效問題及解決

    C++迭代器失效問題及解決

    這篇文章主要介紹了C++迭代器失效問題及解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
    2023-02-02
  • Qt圖形圖像開發(fā)曲線圖表模塊QChart庫基本用法、各個(gè)類之間的關(guān)系說明

    Qt圖形圖像開發(fā)曲線圖表模塊QChart庫基本用法、各個(gè)類之間的關(guān)系說明

    這篇文章主要介紹了Qt圖形圖像開發(fā)曲線圖表模塊QChart庫基本用法、各個(gè)類之間的關(guān)系說明,需要的朋友可以參考下
    2020-03-03
  • 計(jì)時(shí)器的time_t和clock_t 的兩種實(shí)現(xiàn)方法(推薦)

    計(jì)時(shí)器的time_t和clock_t 的兩種實(shí)現(xiàn)方法(推薦)

    下面小編就為大家?guī)硪黄?jì)時(shí)器的time_t和clock_t 的兩種實(shí)現(xiàn)方法(推薦)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2016-10-10
  • C++概念重載、覆蓋、隱藏的使用說明

    C++概念重載、覆蓋、隱藏的使用說明

    本篇文章介紹了，在C++中概念重載、覆蓋、隱藏的使用分析說明。需要的朋友參考下
    2013-05-05
  • 詳解C++之函數(shù)重載

    詳解C++之函數(shù)重載

    這篇文章主要介紹了c++函數(shù)重載的相關(guān)知識，文章講解的非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下
    2020-06-06
  • C++實(shí)現(xiàn)順序表的方法

    C++實(shí)現(xiàn)順序表的方法

    本文給大家?guī)砹薈++實(shí)現(xiàn)順序表的方法，代碼簡單易懂，附有注釋，感興趣的朋友一起看下吧
    2016-08-08
  • C++實(shí)現(xiàn)AVL樹的完整代碼

    C++實(shí)現(xiàn)AVL樹的完整代碼

    AVL樹是高度平衡的而二叉樹。它的特點(diǎn)是：AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為1。 今天通過本文給大家分享C++實(shí)現(xiàn)AVL樹的完整代碼，感興趣的朋友一起看看吧
    2021-06-06
  • C++中的strcmp函數(shù)

    C++中的strcmp函數(shù)

    strcmp函數(shù)是C++標(biāo)準(zhǔn)庫中用于字符串比較的重要函數(shù),在C++中,字符串比較是一項(xiàng)常見的操作,用于判斷兩個(gè)字符串是否相等或者大小關(guān)系,本文介紹C++中的strcmp函數(shù),感興趣的朋友一起看看吧
    2024-03-03
  • C語言根據(jù)協(xié)議分割獲取字符串單元的實(shí)現(xiàn)代碼

    C語言根據(jù)協(xié)議分割獲取字符串單元的實(shí)現(xiàn)代碼

    今天小編就為大家分享一篇關(guān)于C語言根據(jù)協(xié)議分割獲取字符串單元的實(shí)現(xiàn)代碼，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • C++命令行解析包gflags的使用教程

    C++命令行解析包gflags的使用教程

    這篇文章主要給大家介紹了關(guān)于C++命令行解析包gflags的使用教程，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-11-11

最新評論