Submission #71170804

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
struct State{
    int len,link;
    int next[26];
};
const int MAXN = 200005;
State st[MAXN * 2];
int sz,last;
int memo[MAXN * 2];
void sam_init(){
    st[0].len = 0;
    st[0].link = -1;
    memset(st[0].next,-1,sizeof(st[0].next));
    sz = 1;
    last = 0;
}
void sam(char c){
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    memset(st[cur].next,-1,sizeof(st[cur].next));
    int p = last;
    int code = c - 'a';
    while(p != -1 && st[p].next[code] == -1){
        st[p].next[code] = cur;
        p = st[p].link;
    }
    if(p == -1){
        st[cur].link = 0;
    }
    else{
        int q = st[p].next[code];
        if(st[p].len + 1 == st[q].len){
            st[cur].link = q;
        }
        else{
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            memcpy(st[clone].next,st[q].next,sizeof(st[q].next));
            st[clone].link = st[q].link;
            while(p != -1 && st[p].next[code] == q){
                st[p].next[code] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

int game(int u){
    if(memo[u] != -1) return memo[u];
    bool cfo = false;
    for(int i=0;i<26;i++){
        if(st[u].next[i] != -1){
            if(game(st[u].next[i]) == 0){
                cfo = true;
                break;
            }
        }
    }
    return memo[u] = (cfo ? 1 : 0);
}

void solve(){
    string s;
    cin>>s;
    sam_init();
    for(char c : s){
        sam(c);
        //cout<<c<<endl;
    }
    for(int i=0;i<sz;i++) memo[i] = -1;
    if(game(0))
        cout << "Alice" << endl;
    else
        cout << "Bob" << endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

Submission Info

Judge Result