首页 > 代码库 > 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