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