← 返回题目列表

AtCoder · abc433_g

G. 子串游戏

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个字符串 S 由小写英文字母组成。

Alice 和 Bob 使用该字符串玩以下游戏。

  • 准备一个空字符串 T.
  • 从 Alice 开始,他们轮流玩。
  • 每回合,玩家选择一个小写英文字母并将所选字母连接到 T。在这里,玩家不能采取这样的行动: 连接后的 T 不是以下的子串 S.

无法先行动的玩家失败。

确定当两名玩家都发挥最佳状态时哪个玩家将获胜。

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\le T\le 10^5
  • T 是一个整数。
  • S 是由小写英文字母组成的字符串,长度介于 1 和 2\times 10^5,包括在内。
  • 的长度总和 S 所有测试用例最多 4\times 10^5.

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出。

S

输出

按顺序输出测试用例的答案,以换行符分隔。

对于每个测试用例,输出 Alice 如果当两个玩家都发挥最佳状态时爱丽丝获胜,并且 Bob 如果鲍勃获胜。


样本输入 1

4
ooxo
abrakadabra
atcoderbeginnercontest
baabca

示例输出 1

Bob
Alice
Alice
Bob

考虑第一个测试用例。

例如,游戏进行如下。

  • 爱丽丝选择 x. T= x.
  • 鲍勃选择 o. T= xo.
  • 无论Alice选择哪个小写英文字母并连接到末尾 T, T 不会是以下的子串 S,因此 Alice 无法移动。至此,鲍勃获胜。

在这个测试用例中,无论 Alice 如何玩,Bob 都可以获胜。因此,输出 Bob.