題目鏈接

題目鏈接 http://acm.hdu.edu.cn/showproblem.php?pid=1711

題意

裸KMP算法

時間復(fù)雜度

O(m+n)

代碼如下（G++）

#include <iostream> #include "string.h" using namespace std;int a[1000010]; int b[10010]; int next0[10010];int T,N,M; void get_next(){int i = 0;int j = -1;next0[0] = -1;while(i < M){if(j == -1||b[i] == b[j]){i++;j++; next0[i] = j;}else{j = next0[j];} // cout << i << " " << j << endl;} }int KMP(){int i = 0;int j = 0;while(i < N && j < M){if(j == -1 or a[i] == b[j])++i,++j;elsej = next0[j];}if(M == j) return i-j;else return -2; }int main() {ios::sync_with_stdio(false);cin >> T;while(T--){cin >> N >> M;for(int i = 0;i < N; ++i) cin >> a[i];for(int j = 0;j < M; ++j) cin >> b[j];get_next();cout << KMP()+1 << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【HDU 1711】Number Sequence（裸KMP算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。