首页 > 代码库 > HDU 1711 Number Sequence(KMP模板)

HDU 1711 Number Sequence(KMP模板)

 

http://acm.hdu.edu.cn/showproblem.php?pid=1711

这道题就是一个KMP模板。

 1 #include<iostream>  2 #include<cstring> 3 using namespace std; 4  5 const int maxn = 1000000+5; 6  7 int n,m; 8  9 int next[maxn];10 int a[maxn], b[maxn];11 12 void get_next()13 {14     int i = -1, j = 0;15     ::next[0] = -1;16     while (j < m)17     {18         if (i == -1 || b[i] == b[j])19             ::next[++j] = ++i;20         else21             i = ::next[i];22     }23 }24 25 26 int kmp()27 {28     int i = 0, j = 0;29     while (i < n)30     {31         if (j == -1 || a[i] == b[j])32         {33             i++;34             j++;35         }36         else37             j = ::next[j];38         if (j == m)39             return i;40     }41     return -1;42 }43 44 int main()45 {46     //freopen("D:\\txt.txt", "r", stdin);47     int t;48     cin >> t;49     while (t--)50     {51         cin >> n >> m;52         for (int i = 0; i < n; i++)53             cin >> a[i];54         for (int i = 0; i < m; i++)55             cin >> b[i];56         get_next();57         int k=kmp();58         if (k!=-1)  cout << k-m+1 << endl;59         else cout << "-1" << endl;60     }61     return 0;62 }

 

HDU 1711 Number Sequence(KMP模板)