首页 > 代码库 > Sicily 1282. Computer Game
Sicily 1282. Computer Game
题目地址:1282. Computer Game
思路:
KMP算法,网上有很多资料,参考了一些网上的解题,收获很大,很感谢那些大神们!!!
通过这道题简单说说我对KMP算法的理解吧(大神们勿喷,虽然没人看我的orz~~~~囧)。
首先输入的是要匹配的字符串,如果这个字符串的首字母在整个字符串不重复出现的话,直接一直匹配下去即可。
诶,那重复出现了怎么办,那就从最后一个重复出现的重新开始匹配,那么这就找到优化算法的好方法了,KMP算法的精髓大致是这样的。
这道题具体代码如下:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int main() { 6 int len1, len2; 7 while (cin >> len1) { 8 int code[60001] = {0}; 9 int next[60001] = {0};10 for (int i = 1; i <= len1; i++) {11 scanf("%d", &code[i]);12 }13 int index = 0;14 for (int i = 2; i <= len1; i++) {15 index = code[index+1] == code[i] ? index+1 : 0;16 next[i] = index;17 }18 cin >> len2;19 index = 0;20 int test, result;21 for (int i = 1; i <= len2; i++) {22 scanf("%d", &test);23 if (index != len1) {24 index = code[index+1] == test ? index+1 : next[index];25 if (index == len1) {26 result = i-len1;27 }28 }29 }30 index == len1 ? cout << result << endl : cout << "no solution\n";31 }32 33 return 0;34 }
Sicily 1282. Computer Game
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。