程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Sicily 1282. Computer Game,sicily1282

Sicily 1282. Computer Game,sicily1282

編輯:C++入門知識

Sicily 1282. Computer Game,sicily1282


題目地址: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 } 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved