[CF1476E] Pattern Matching

[CF1476E] Pattern Matching - Trie,拓扑排序

Description

给定 (n) 个模式串 (p_i) 和 (m) 个字符串 (s_i)，其中 (p_i) 两两不同。每个模式串和字符串都包含 (k) 个字符。其中模式串中可以含通配符（用下划线表示，可以匹配任何字符），剩余字符都为小写英文字母。同时给定 (n) 个数 (mt_i)，要求重新排列模式串使得 (s_j) 匹配到的第一个模式串为 (p_{mt_j})。请判断是否存在排列方案满足如上要求，能的话请输出方案。

Solution

拓扑排序，需要预处理每个 str 匹配了哪些 pat，对 pat 建立 Trie 树即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 5;

int n_pat, n_str, len;

string pat[N], str[N];
int lim[N];

int ind = 1, ch[N * 5][27], val[N * 5], vis[N], deg[N];

vector<int> g[N];
vector<int> seq;

void insert(string s, int id)
{
    int p = 1;
    for (int i = 0; i < s.size(); i++)
    {
        int c = s[i] - 'a';
        if (s[i] == '_')
            c = 26;
        if (ch[p][c] == 0)
            ch[p][c] = ++ind;
        p = ch[p][c];
    }
    val[p] = id;
}

void find_matches(string s, int i, int p, vector<int> &ans)
{
    if (p == 0)
    {
        return;
    }
    if (i == len)
    {
        if (val[p])
            ans.push_back(val[p]);
    }
    else
    {
        find_matches(s, i + 1, ch[p][s[i] - 'a'], ans);
        find_matches(s, i + 1, ch[p][26], ans);
    }
}

void dfs(int p)
{
    vis[p] = 1;
    for (int q : g[p])
    {
        if (vis[q])
            continue;
        dfs(q);
    }
    seq.push_back(p);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n_pat >> n_str >> len;

    for (int i = 1; i <= n_pat; i++)
    {
        cin >> pat[i];
        insert(pat[i], i);
    }

    for (int i = 1; i <= n_str; i++)
    {
        cin >> str[i] >> lim[i];
        vector<int> matches;
        find_matches(str[i], 0, 1, matches);
        int flag = 0;
        for (auto j : matches)
        {
            if (j == lim[i])
            {
                flag = 1;
            }
            else
            {
                g[lim[i]].push_back(j);
                deg[j]++;
            }
        }
        if (flag == 0)
        {
            cout << "NO" << endl;
            return 0;
        }
    }

    // toposort
    for (int i = 1; i <= n_pat; i++)
    {
        if (deg[i] || vis[i])
            continue;
        dfs(i);
    }
    reverse(seq.begin(), seq.end());

    set<int> s;
    if (seq.size())
        for (int i = seq.size() - 1; i >= 0; i--)
        {
            s.insert(seq[i]);
            for (int q : g[seq[i]])
            {
                if (s.find(q) == s.end())
                {
                    cout << "NO" << endl;
                    return 0;
                }
            }
        }

    if (seq.size() != n_pat)
    {
        cout << "NO" << endl;
    }
    else
    {
        cout << "YES" << endl;
        for (auto i : seq)
            cout << i << " ";
        cout << endl;
    }
}