Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define LOG(FMT...) fprintf(stderr, FMT)
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- template <class T>
- istream& operator>>(istream& is, vector<T>& v) {
- for (T& x : v)
- is >> x;
- return is;
- }
- template <class T>
- ostream& operator<<(ostream& os, const vector<T>& v) {
- if (!v.empty()) {
- os << v.front();
- for (int i = 1; i < v.size(); ++i)
- os << ' ' << v[i];
- }
- return os;
- }
- const int N = 752, L = 10000010;
- int n, rt, cnt;
- int pos[N];
- char s[L];
- int ch[L][2];
- bitset<N> trans[N];
- bool vis[N];
- int dfn[N];
- int fail[L], prt[L], belongs[L], lst[L];
- int f[N];
- int sz[N];
- bool g[N][N];
- int match[N];
- bool matched[N];
- bool vx[N], vy[N];
- void dfs(int u) {
- static int t;
- vis[u] = true;
- for (int v = 1; v <= n; ++v)
- if (trans[u][v]) {
- if (!vis[v])
- dfs(v);
- trans[u] |= trans[v];
- }
- dfn[++t] = u;
- }
- bool hgy(int u) {
- vis[u] = true;
- for (int v = 1; v <= n; ++v)
- if (g[u][v]) {
- if (!match[v] || (!vis[match[v]] && hgy(match[v]))) {
- match[v] = u;
- return true;
- }
- }
- return false;
- }
- void dfs2(int u) {
- vy[u] = true;
- }
- int main() {
- #ifdef LBT
- freopen("test.in", "r", stdin);
- int nol_cl = clock();
- #endif
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- rt = cnt = 1;
- for (int i = 1; i <= n; ++i) {
- cin >> s;
- int o = rt;
- for (char* p = s; *p; ++p) {
- if (!ch[o][*p - 'a']) {
- ch[o][*p - 'a'] = ++cnt;
- prt[cnt] = o;
- }
- o = ch[o][*p - 'a'];
- }
- pos[i] = o;
- belongs[o] = i;
- }
- queue<int> q;
- for (int i = 0; i < 2; ++i)
- if (ch[rt][i]) {
- fail[ch[rt][i]] = rt;
- q.push(ch[rt][i]);
- }
- while (!q.empty()) {
- int o = q.front();
- q.pop();
- for (int i = 0; i < 2; ++i)
- if (ch[o][i]) {
- int k = fail[o];
- while (k != rt && !ch[k][i]) k = fail[k];
- k = fail[ch[o][i]] = ch[k][i] ? ch[k][i] : rt;
- lst[ch[o][i]] = belongs[k] ? belongs[k] : lst[k];
- q.push(ch[o][i]);
- }
- }
- for (int i = 1; i <= n; ++i)
- for (int o = pos[i]; o; o = prt[o])
- if (lst[o])
- trans[i].set(lst[o]);
- else if (o != pos[i] && belongs[o])
- trans[i].set(belongs[o]);
- for (int i = 1; i <= n; ++i)
- if (!vis[i])
- dfs(i);
- cerr << "good\n";
- int ans = 0;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= n; ++j)
- g[i][j] = trans[i][j];
- memset(vis, 0, sizeof(vis));
- if (hgy(i)) {
- ++ans;
- }
- }
- for (int i = 1; i <= n; ++i)
- if (match[i]) matched[match[i]] = true;
- for (int i = 1; i <= n; ++i) {
- if (!match[i])
- dfs2(i);
- }
- cout << n - ans << '\n';
- for (int i = 1; i <= n; ++i)
- if (!vx[i] && !vy[i]) cout << i << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment