andyli

题解 UVA11019 【Matrix Matcher】
要想整个矩阵匹配,至少各行都得匹配。所以先把$P$的每行看做一个模式串构造出$AC$自动机,然后在$T$中的各行逐...
扫描右侧二维码阅读全文
27
2019/06

题解 UVA11019 【Matrix Matcher】

要想整个矩阵匹配,至少各行都得匹配。所以先把$P$的每行看做一个模式串构造出$AC$自动机,然后在$T$中的各行逐一匹配,找到$P$中每一行的所有匹配点。
只要在匹配时做一些附加的操作,就可以把匹配出来的单一的行拼成矩形。用一个$cnt[r][c]$表示$T$中以$(r,c)$为左上角、与$P$等大的矩形中有多少个完整的行和$P$对应位置的行完全相同。当$P$的第$i$行出现在$T$的第$r$行,起始列编号为$c$时,意味着$cnt[r-i][c]$应当加$1$(行列均从$0$开始编号)。所有匹配结束时,$cnt[r][c]=x$($P$的行数)的那些$(r,c)$就是一个二维匹配点。
这个算法的时间复杂度为$O(nm+xy)$,达到了理论下限(最坏情况下,必须检查$T$和$P$的每一个字符)。
注意代码中的report函数不能使用递归形式,只能用手写栈来模拟实现。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxnode = 10005;

// AC自动机每找到一个匹配会调用一次,结束位置为pos,val为v
void process_match(int pos, int v);
struct AhoCorasickAutomata
{
    int ch[maxnode][26];
    int f[maxnode];     // fail函数
    int val[maxnode];   // 每个字符串的结尾结点都有一个非0的val
    int last[maxnode];  // 输出链表的下一个结点
    int sz;
    void init()
    {
        sz = 1;
        memset(ch, 0, sizeof(ch));
        memset(val, 0, sizeof(val));
        memset(last, 0, sizeof(last));
        memset(f, 0, sizeof(f));
    }
    // 字符c的编号
    int idx(char c) { return c - 'a'; }
    // 插入字符串。v必须非0
    void insert(char* s, int v)
    {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; i++)
        {
            int c = idx(s[i]);
            if (!ch[u][c])
            {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = v;
    }
    void report(int pos, int j)
    {
        stack<int> st;
        st.push(j);
        while (!st.empty())
        {
            j = st.top();
            st.pop();
            if (j)
                process_match(pos, val[j]), st.push(last[j]);
        }
        // if (j)
        //{
        //    process_match(pos, val[j]);
        //    report(pos, last[j]);
        //}
        // 用系统栈会RE
    }
    // 在T中找模板
    void find(char* T)
    {
        int n = strlen(T);
        int j = 0;  // 当前结点编号,初始为根结点
        for (int i = 0; i < n; i++)
        {  // 文本串当前指针
            int c = idx(T[i]);
            while (j && !ch[j][c])
                j = f[j];  // 顺着细边走,直到可以匹配
            j = ch[j][c];
            if (val[j])
                report(i, j);
            else if (last[j])
                report(i, last[j]);  // 找到了!
        }
    }
    // 计算fail函数
    void getFail()
    {
        queue<int> q;
        f[0] = 0;
        // 初始化队列
        for (int c = 0; c < 26; c++)
        {
            int u = ch[0][c];
            if (u)
            {
                f[u] = 0;
                q.push(u);
                last[u] = 0;
            }
        }
        // 按BFS顺序计算fail
        while (!q.empty())
        {
            int r = q.front();
            q.pop();
            for (int c = 0; c < 26; c++)
            {
                int u = ch[r][c];
                if (!u)
                    continue;
                q.push(u);
                int v = f[r];
                while (v && !ch[v][c])
                    v = f[v];
                f[u] = ch[v][c];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }
} ac;

const int maxn = 1010, maxx = 110;
char text[maxn][maxn], P[maxx][maxx];

int repr[maxx];  // repr[i]为模板第i行的“代表元”
int Next[maxx];  // Next[i]为模板中与第i行相等的下一个行编号
int len[maxx];   // 模板各行的长度

int tr;  // 当前文本行编号
int cnt[maxn][maxn];
void process_match(int pos, int v)
{
    int pr = repr[v - 1];  // 匹配到得模板行编号
    int c = pos - len[pr] + 1;
    while (pr >= 0)
    {
        if (tr >= pr)  // P的行pr出现在在T的tr行,起始列编号为c
            cnt[tr - pr][c]++;
        pr = Next[pr];
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", text[i]);
        int x, y;
        scanf("%d%d", &x, &y);
        ac.init();
        memset(Next, -1, sizeof(Next));
        for (int i = 0; i < x; i++)
        {
            scanf("%s", P[i]);
            len[i] = strlen(P[i]);
            repr[i] = i;
            Next[i] = -1;
            for (int j = 0; j < i; j++)
                if (!strcmp(P[i], P[j]))
                {
                    repr[i] = j;
                    Next[i] = Next[j];
                    Next[j] = i;
                    break;
                }
            if (repr[i] == i)
                ac.insert(P[i], i + 1);
        }
        ac.getFail();
        memset(cnt, 0, sizeof(cnt));
        for (tr = 0; tr < n; tr++)
            ac.find(text[tr]);
        int ans = 0;
        for (int i = 0; i < n - x + 1; i++)
            for (int j = 0; j < m - y + 1; j++)
                if (cnt[i][j] == x)
                    ans++;
        printf("%d\n", ans);
    }
    return 0;
}
Last modification:June 27th, 2019 at 02:11 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment