首页 > 代码库 > 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模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。