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

KMP 算法實例詳解

 更新時間:2017年07月27日 10:47:56   投稿:lqh  
這篇文章主要介紹了KMP 算法實例詳解的相關(guān)資料,MP的關(guān)鍵是求出next的值、先預(yù)處理出next的值,需要的朋友可以參考下

KMP 算法實例詳解

KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其對于任何模式和目標(biāo)序列,都可以在線性時間內(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 算法的實例詳解本站關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的文章還有很多,希望大家搜索查閱,感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

相關(guān)文章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最新評論