A String Game(后缀自动机+SG函数)

描述

传送门:是男人就过8题 - Problem A

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.

Sample Input

1
2
3
4
5
6
aaaa
1
a
abcabd
1
a

Sample Output

1
2
Alice
Bob

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1 << 17;
struct SAM
{
int len[maxn << 1], link[maxn << 1], ch[maxn << 1][26];
int sz, rt, last;
int newnode(int x = 0)
{
len[sz] = x;
link[sz] = -1;
memset(ch[sz], -1, sizeof(ch[sz]));
return sz++;
}
void init()
{
sz = last = 0, rt = newnode();
memset(dp, -1, sizeof(dp));
}
void extend(int c)
{
int np = newnode(len[last] + 1);
int p;
for (p = last; ~p && ch[p][c] == -1; p = link[p]) ch[p][c] = np;
if (p == -1)
link[np] = rt;
else
{
int q = ch[p][c];
if (len[p] + 1 == len[q])
link[np] = q;
else
{
int nq = newnode(len[p] + 1);
memcpy(ch[nq], ch[q], sizeof(ch[q]));
link[nq] = link[q], link[q] = link[np] = nq;
for (; ~p && ch[p][c] == q; p = link[p]) ch[p][c] = nq;
}
}
last = np;
}
int dp[maxn << 1];
int find(const char* s)
{
int u = rt;
for (int i = 0; s[i]; i++) u = ch[u][s[i] - 'a'];
return dfs(u);
}
int dfs(int u)
{
if (~dp[u]) return dp[u];
set<int> s;
for (int i = 0; i < 26; i++)
if (~ch[u][i])
s.insert(dfs(ch[u][i]));
for (int i = 0;; i++)
if (s.find(i) == s.end())
return dp[u] = i;
}
} sam;

char s[maxn], t[maxn];

int main()
{
while (~scanf("%s", t))
{
sam.init();
for (int i = 0; t[i]; i++) sam.extend(t[i] - 'a');
int n;
scanf("%d", &n);
int sum = 0;
while (n--)
{
scanf("%s", s);
sum ^= sam.find(s);
}
puts(sum ? "Alice" : "Bob");
}
}
捐助作者
0%