# 描述

Recently Alice and Bob are playing a game about strings. Before starting the game, they should prepare $n$ strings $s_1$​, $s_2$​, …, $s_n$​ and a target string $t$. It’s promised that each of these $n$ strings is a substring of $t$.

When the game begins, they do the following things alternately while Alice starts first:

• Choose a string $s_i$​ from the $n$ strings;
• Append one letter to the chosen string;
• The new string must also be a substring of $t$.

If the above things cannot be completed, the player loses the game. Suppose Alice and Bob both use optimal strategy, find who will win the game.

## Input

The input consists of multiple test cases.

Each test case begins with the non-empty target string $t$, whose length will not exceed $100000$. The second line contains an integer $n$ ($1≤n≤100$), the number of strings they prepared. Then $n$ lines follow. The $i$-th line of the following $n$ lines is the string $s_i$​. The input guarantees that each of the $n$ strings must be a non-empty substring of $t$.

The total length of all strings will not exceed $30000000$.

## Output

For each test case, output the winner “Alice” or “Bob” (without quotes) in one line.

# 思路

• 首先可以想到，在一个串后面不断加字母，最后一定会加成目标串的后缀。
• 于是对于每一个串，我们可以考虑成在后缀自动机上的某个结点，两人在后缀自动机上进行博弈。
• DAG上的博弈就是一个套路题了，直接记忆化搜索即可。
• 由于这里是多图组合，我们不能对一个图直接求胜负态，需要把图上每个点的SG值求出来。
• 整个游戏的胜负就是每个子游戏的NIM和咯～

0%