小红的字符串匹配

思路

这道题乍一看需要对每个查询字符串 判断很多前缀和后缀，好像很复杂。我们来一步步拆解。

问题本质是什么？

对于字符串 ，我们要检查两件事：

  1. 的某个长度 的前缀是 的子串
  2. 的某个长度 的后缀是 的子串

只要任意一个成立就输出 YES。

前缀的关键观察

如果我们从左到右逐字符把 喂进 的后缀自动机（SAM），只要走到第 步还没有失配，就说明 （长度为 的前缀）是 的子串，可以直接返回 YES。如果在某一步失配了，那更长的前缀也不可能是 的子串（因为前缀有包含关系），可以直接返回 NO。

后缀怎么处理？

后缀的判断可以巧妙转化： 的后缀是 的子串，等价于 的前缀是 的子串。所以我们只需要对 再建一个 SAM，然后用同样的方法检查 的前缀即可。

后缀自动机（SAM）是什么？

SAM 是一种能在 时间和空间内建好的数据结构，它能识别 的所有子串。给定一个模式串，沿着 SAM 的转移边走，如果每一步都有对应的转移，就说明这个模式串是 的子串。

复杂度分析

  • 建两个 SAM：
  • 每个查询：
  • 总复杂度：

代码

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

struct SAM {
    struct State {
        int len, link;
        map<char, int> next;
    };
    vector<State> st;
    int last;

    void init() {
        st.push_back({0, -1, {}});
        last = 0;
    }

    void extend(char c) {
        int cur = st.size();
        st.push_back({st[last].len + 1, -1, {}});
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next});
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = clone;
                st[cur].link = clone;
            }
        }
        last = cur;
    }

    bool checkPrefix(const string& t, int k) {
        if ((int)t.size() < k) return false;
        int cur = 0;
        for (int i = 0; i < (int)t.size(); i++) {
            if (st[cur].next.count(t[i])) {
                cur = st[cur].next[t[i]];
                if (i + 1 >= k) return true;
            } else {
                return false;
            }
        }
        return false;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int q, k;
    cin >> q >> k;

    SAM sam1;
    sam1.init();
    for (char c : s) sam1.extend(c);

    SAM sam2;
    sam2.init();
    string rs(s.rbegin(), s.rend());
    for (char c : rs) sam2.extend(c);

    while (q--) {
        string t;
        cin >> t;
        bool ok = sam1.checkPrefix(t, k);
        if (!ok) {
            string rt(t.rbegin(), t.rend());
            ok = sam2.checkPrefix(rt, k);
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] samLen, samLink;
    static int[][] samCh;
    static int samSz, samLast;

    static void samInit(int maxNodes) {
        samLen = new int[maxNodes];
        samLink = new int[maxNodes];
        samCh = new int[maxNodes][26];
        for (int[] row : samCh) Arrays.fill(row, -1);
        Arrays.fill(samLink, -1);
        samSz = 1;
        samLast = 0;
    }

    static void samExtend(int c) {
        int cur = samSz++;
        samLen[cur] = samLen[samLast] + 1;
        int p = samLast;
        while (p != -1 && samCh[p][c] == -1) {
            samCh[p][c] = cur;
            p = samLink[p];
        }
        if (p == -1) {
            samLink[cur] = 0;
        } else {
            int q = samCh[p][c];
            if (samLen[p] + 1 == samLen[q]) {
                samLink[cur] = q;
            } else {
                int clone = samSz++;
                samLen[clone] = samLen[p] + 1;
                samLink[clone] = samLink[q];
                System.arraycopy(samCh[q], 0, samCh[clone], 0, 26);
                while (p != -1 && samCh[p][c] == q) {
                    samCh[p][c] = clone;
                    p = samLink[p];
                }
                samLink[q] = clone;
                samLink[cur] = clone;
            }
        }
        samLast = cur;
    }

    static boolean checkPrefix(int[][] ch, String t, int k) {
        if (t.length() < k) return false;
        int cur = 0;
        for (int i = 0; i < t.length(); i++) {
            int c = t.charAt(i) - 'a';
            if (ch[cur][c] != -1) {
                cur = ch[cur][c];
                if (i + 1 >= k) return true;
            } else {
                return false;
            }
        }
        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String s = br.readLine().trim();
        int n = s.length();
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int q = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        // Build SAM on s
        samInit(2 * n + 5);
        for (int i = 0; i < n; i++) {
            samExtend(s.charAt(i) - 'a');
        }
        int[][] ch1 = new int[samSz][26];
        for (int i = 0; i < samSz; i++) {
            System.arraycopy(samCh[i], 0, ch1[i], 0, 26);
        }

        // Build SAM on reversed s
        samInit(2 * n + 5);
        for (int i = n - 1; i >= 0; i--) {
            samExtend(s.charAt(i) - 'a');
        }
        int[][] ch2 = new int[samSz][26];
        for (int i = 0; i < samSz; i++) {
            System.arraycopy(samCh[i], 0, ch2[i], 0, 26);
        }

        while (q-- > 0) {
            String t = br.readLine().trim();
            boolean ok = checkPrefix(ch1, t, k);
            if (!ok) {
                String rt = new StringBuilder(t).reverse().toString();
                ok = checkPrefix(ch2, rt, k);
            }
            sb.append(ok ? "YES" : "NO").append('\n');
        }

        System.out.print(sb);
    }
}

复杂度

  • 时间复杂度: ，其中 为字符集大小。建 SAM 为 ，每个查询为 。
  • 空间复杂度: ，SAM 的状态数为 ，每个状态存储 条转移边。