GMOJ 3569. 正則運算式-有解無憂

Input

Output

對于每一組資料，如果正則運算式r能表示字串str，輸出“Yes”，否則輸出“No”，

Solution

考慮對于題目所給的正則運算式建一個自動機，

設當前在處理 S[l...r] ，last 指向當前自動機要繼續擴展的點(ed)，

1.串聯

last 向新增的 st 連一條空邊，然后將 last 設為 ed

2.單個字符a

新建st、ed節點，然后連一條權值為此字符的邊，

3." ( "

找到與之對應的")"，新建一對st、ed節點，對于括號中間的字串dg處理

4.并聯

將 last （當前的 ed）與 S[l...r]的 ed 連一條空邊，然后將 last 重設為S[l...r]的 st

5. " + "

當前 last 指向的 ed 向對應 st 連一條空邊

6. " * "

第一步與 + 操作相同，但要多連一條 st -> ed 的空邊

7. 別忘了最后將連一條 last 到S[l...r]的 ed 的空邊哦~

PS：每次操作完后如果要更新 last 不要忘記，對于每一個要處理的字串S[l, r]，它們的 last 是獨立的；

對于部分操作（例如2、3操作），其實是伴隨著串聯操作的，

最后我們需要判斷構造出來的自動機十分能構造出字串 str，

設 f[i][j] 表示 str 匹配到第i位，自動機上匹配到 j是否可行，轉移顯然，注意空邊可以直接轉移過去

最后看 f[n][ed] 是否為1即可

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define N 100
#define M 1000

#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define Mes(a, x) memset(a, x, sizeof a)

struct EDGE { int next, to; char c; } edge[M + 1];

struct Edge { int next, to; } g[M + 1];

int head[M + 1], h[M + 1], f[N + 1][M + 1], Next[M + 1], pre[M + 1];

char ch[N + 1];

int tot = 0, n, m;

struct Arr { int st, ed; } last_d;

int cnt_edge = 0;
void Add(int u, int v, char c) { edge[ ++ cnt_edge ] = (EDGE) { head[u], v, c }, head[u] = cnt_edge; }

int cnt_g = 0;
void Add(int u, int v) { g[ ++ cnt_g ] = (Edge) { h[u], v }, h[u] = cnt_g; }

Arr Insert(int l, int r) {
    if (l > r) return (Arr) { 0, 0 };
    int st = ++ tot, ed = ++ tot;
    Next[ed] = st;
    if (l == r) {
        Add(st, ed, ch[l]);
        return (Arr) { st, ed };
    }
    int last = st;
    fo(i, l, r) {
        if (ch[i] == '(') {
            int s = 1;
            fo(j, i + 1, r) {
                s += ch[j] == ')' ? -1 : (ch[j] == '(' ? 1 : 0);
                if (! s) {
                    Arr d = Insert(i + 1, j - 1);
                    if (! d.st) break;
                    Add(last, d.st), pre[d.st] = last;
                    last = d.ed;
                    i = j;
                    break;
                }
            }
        } else if (ch[i] == '|') {
            Add(last, ed); last = st;
        } else if (ch[i] == '*') {
            Add(last, Next[last]), Add(Next[last], last);
        } else if (ch[i] == '+') {
            Add(last, Next[last]);
        } else if (ch[i] == ')') 
            continue;
        else {
            Arr d = Insert(i, i);
            Add(last, d.st), pre[d.st] = last; 
            last = d.ed;
        }
    }
    Add(last, ed);
    return (Arr) { st, ed };
}

bool Dfs(int t, int x) {
    if (t > m && x == last_d.ed) return 1;
    if (f[t][x]) return 0;
    f[t][x] = 1;
    if (t <= m) {
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].c == ch[t] && Dfs(t + 1, edge[i].to))
                return 1;
    }
    for (int i = h[x]; i; i = g[i].next)
        if (Dfs(t, g[i].to))
            return 1;
    return 0;
}

int main() {

    while (~ scanf("%s\n", ch + 1)) {
        Mes(head, 0), Mes(h, 0), tot = 0;
        n = strlen(ch + 1);
        last_d = Insert(1, n);
        scanf("%s\n", ch + 1);
        m = strlen(ch + 1);
        Mes(f, 0);
        puts(Dfs(last_d.st, 1) ? "Yes" : "No");
    }

    return 0;
}

View Code

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3877.html

標籤：其他

上一篇：0409. Longest Palindrome (E)

下一篇：CF 1391D 505