第八届福建省大学生程序设计竞赛-重现赛（感谢承办方厦门理工学院）
思维题+kmp 之前一直T 后来想了下 strstr的复杂度是O(n*m) 才想到kmp 只要Alice的串比Bob长 并且Bob的串是Alice的串或反转串的子串 赢家就是Alice 因为用到了strrev 提交的时候要用VC++
#include<stdio.h> #include<iostream> #include<iostream> #include<math.h> #include<string> #include<queue> #include<stack> #include <cstring> using namespace std; typedef long long ll; const ll inf = 0x3f3f3f3f3f3f3f3f ; char ch1[100005] , ch2[100005]; int Next[100005]; void makeNext(const char P[],int next[]) { int q,k; int m = strlen(P); next[0] = 0; for (q = 1,k = 0; q < m; ++q) { while(k > 0 && P[q] != P[k]) k = next[k-1]; if (P[q] == P[k]) { k++; } next[q] = k; } } int kmp(const char T[],const char P[],int next[]) { int n,m; int i,q; n = strlen(T); m = strlen(P); makeNext(P,next); for (i = 0,q = 0; i < n; ++i) { while(q > 0 && P[q] != T[i]) q = next[q-1]; if (P[q] == T[i]) { q++; } if (q == m) { return i-m+1; } } return -1; } int main() { int t; scanf("%d" , &t); while(t--){ scanf("%s%s",ch1,ch2); int len1 = strlen(ch1); int len2 = strlen(ch2); if(len1 < len2){ cout<<"Bob"<<endl; } else{ if(len2 == 1 && ch2[0] == '0'){ cout<<"Alice"<<endl; continue; } int fin1 = kmp(ch1 , ch2 , Next); char str[100005]; strcpy(str,strrev(ch2)); int fin2 = kmp(ch1 , str , Next); if(fin1 != -1 || fin2 != -1) cout<<"Alice"<<endl; else cout<<"Bob"<<endl; } } return 0; }