Submission #71158970

---

Source Code Expand

/* Code By WCM */
/*
Date:
大致思路：
复杂度：
期望得分：
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <vector>
#include <queue>
#include <unordered_map>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long

using namespace std;

inline int read();
void write(int);
void writeln(int);

int T;
string S;
struct SAM {
	struct D {
		int nxt[26], lk, len;
		D() : lk(-1), len(0) { fill(nxt, nxt + 26, -1); }
	};
	vector <D> st;
	int lst;
	explicit SAM(int mxl = 0) { 
		st.reserve(2 * mxl + 5); st.pb(D()); 
		st[0].lk = -1, st[0].len = 0, lst = 0;
	}
	void extend(int c) {
		int now = st.size();
		st.pb(D()), st[now].len = st[lst].len + 1;
		int pre = lst;
		while(pre != -1 && st[pre].nxt[c] == -1) st[pre].nxt[c] = now, pre = st[pre].lk;
		if(pre == -1) st[now].lk = 0;
		else {
			int suf = st[pre].nxt[c];
			if(st[pre].len + 1 == st[suf].len) st[now].lk = suf;
			else {
				int sz = st.size();
				st.pb(st[suf]), st[sz].len = st[pre].len + 1;
				while(pre != -1 && st[pre].nxt[c] == suf) st[pre].nxt[c] = sz, pre = st[pre].lk;
				st[suf].lk = st[now].lk = sz;
			}
		}
		lst = now;
	}
};

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> T;
	while(T--) {
		cin >> S;
		int n = S.size(), SZ;
		SAM hz(n);
		for(int i = 0; i < n; i++) hz.extend(S[i] - 'a');
		SZ = hz.st.size();
		int mxl = 0;
		for(int i = 0; i < SZ; i++) mxl = max(mxl, hz.st[i].len);
		vector <int> cnt(mxl + 1, 0), ord(SZ);
		for(int i = 0; i < SZ; i++) cnt[hz.st[i].len]++;
		for(int i = 1; i <= mxl; i++) cnt[i] += cnt[i - 1];
		for(int i = SZ - 1; i >= 0; i--) ord[--cnt[hz.st[i].len]] = i;
		vector <bool> dp(SZ, 0);
		for(int i = SZ - 1; i >= 0; i--) {
			int u = ord[i]; bool ww = 0;
			for(int j = 0; j < 26; j++) {
				int v = hz.st[u].nxt[j];
				if(v != -1) if(!dp[v]) { ww = 1; break; }
			}
			dp[u] = ww;
		}
		puts(dp[0] ? "Alice" : "Bob");
	}
	
//	printf("\nThe time used: ");
//	printf("%.2lfs",(double)clock()/CLOCKS_PER_SEC);

	return 0;

}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
	while(ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
	return res * f;
}

void write(int x) {
	static int sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result