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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
| #include <bits/stdc++.h>
using std::cerr; using std::endl;
const int N = 1e7 + 233, M = 755;
int n, st[N], len[N], size; char str[N], buc[N];
int ch[N][2], fail[N], tot, end[N]; std::queue<int> que;
inline void insert(int id) { int now = 0; for (int i = 1; i <= len[id]; ++i) { int c = str[i] - 'a'; if (!ch[now][c]) ch[now][c] = ++tot; now = ch[now][c]; } end[now] = id; }
inline void build() { if (ch[0][0]) que.push(ch[0][0]); if (ch[0][1]) que.push(ch[0][1]); while (!que.empty()) { int x = que.front(); que.pop(); for (int i = 0; i < 2; ++i) { if (!ch[x][i]) ch[x][i] = ch[fail[x]][i]; else { fail[ch[x][i]] = ch[fail[x]][i]; que.push(ch[x][i]); if (!end[ch[x][i]]) end[ch[x][i]] = end[fail[ch[x][i]]]; } } } }
int G[M][M];
inline void match(char str[], int id) { int now = 0; for (int i = 1; i <= len[id]; ++i) { int c = str[i] - 'a'; now = ch[now][c]; if (end[now]) G[id][end[now]] = 1; if (end[fail[now]]) G[id][end[fail[now]]] = 1; } }
int vis[M * 2], mat[M * 2], cnt;
int hungry(int x, int tag) { for (int y = 1; y <= n; ++y) { if (!G[x][y]) continue; if (vis[y + n] != tag) { vis[y + n] = tag; if (!mat[y + n] hungry(mat[y + n], tag)) { mat[x] = y + n, mat[y + n] = x; return 1; } } } return 0; }
int pick[M * 2];
void dfs(int x) { if (vis[x]) return; vis[x] = 1; for (int y = 1; y <= n; ++y) if (G[x][y] && !vis[y + n]) vis[y + n] = 1, dfs(mat[y + n]); }
int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%s", str + 1); len[i] = strlen(str + 1); st[i] = size + 1; for (int j = 1; j <= len[i]; ++j) buc[++size] = str[j]; insert(i); } build(); for (int i = 1; i <= n; ++i) match(buc + st[i] - 1, i); for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) G[i][j] = G[i][k] & G[k][j];
for (int i = 1; i <= n; ++i) G[i][i] = 0; for (int i = 1; i <= n; ++i) cnt += hungry(i, i); printf("%d\n", n - cnt); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; ++i) if (!mat[i]) dfs(i); for (int i = 1; i <= n; ++i) if (vis[i] && !vis[i + n]) printf("%d ", i); putchar('\n'); return 0; }
|