Substring Game

AtCoder

IDabc433_g

Time3000ms

Memory256MB

Difficulty—

You are given a string $S$ consisting of lowercase English letters. Alice and Bob play the following game using this string. * Prepare an empty string $T$. * Starting with Alice, they take turns playing. * On each turn, the player chooses one lowercase English letter and concatenates the chosen letter to the end of $T$. Here, the player cannot take an action such that $T$ after concatenation is not a substring of $S$. The player who cannot make a move first loses. Determine which player will win when both players play optimally. You are given $T$ test cases; solve each of them. ## Constraints * $1\le T\le 10^5$ * $T$ is an integer. * $S$ is a string consisting of lowercase English letters with length between $1$ and $2\times 10^5$, inclusive. * The sum of the lengths of $S$ over all test cases is at most $4\times 10^5$. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case is given in the following format. $S$ [samples]

Samples

Input #1

4
ooxo
abrakadabra
atcoderbeginnercontest
baabca

Output #1

Bob
Alice
Alice
Bob

Consider the first test case.
For example, the game proceeds as follows.

*   Alice chooses `x`. $T=$ `x`.
*   Bob chooses `o`. $T=$ `xo`.
*   No matter which lowercase English letter Alice chooses and concatenates to the end of $T$, $T$ will not be a substring of $S$, so Alice cannot make a move. At this point, Bob wins.

In this test case, Bob can win no matter how Alice plays. Therefore, output `Bob`.

API Response (JSON)

{
  "problem": {
    "name": "Substring Game",
    "description": {
      "content": "You are given a string $S$ consisting of lowercase English letters. Alice and Bob play the following game using this string. *   Prepare an empty string $T$. *   Starting with Alice, they take turns ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc433_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S$ consisting of lowercase English letters.\nAlice and Bob play the following game using this string.\n\n*   Prepare an empty string $T$.\n*   Starting with Alice, they take turns ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments