all string

KMP

前置

• Boder 前缀等于后缀
  S = bbabbab, 有1和4
• 周期和循环节
  p是S的周期 == |S|-p是S的Boder
• Border不具二分性
• Boeder具有传递性Border的Border也是Border

NEXT数组

next[i] = Preffix[i]的非平凡最大Border
next[1] = 0

next[i]遍历Prefix[i - 1]的所有Border

利用势能分析O(N),常数在2

vector<int> prefixFunction(const string &s) {
    vector<int> pi(s.size());
    for (int i = 1, j = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        pi[i] = j += s[i] == s[j];
    }
    return pi;
}
 
vector<int> match(const string &s, const string &t) {
    auto pi = prefixFunction(t);
    vector<int> ans;
    for (int i = 0, j = 0; i < s.size(); i++) {
        while (j > 0 && s[i] != t[j]) {
            j = pi[j - 1];
        }
        j += s[i] == t[j];
        if (j == t.size()) {
            ans.push_back(i - j + 1);
            j = pi[j - 1];
        }
    }
    return ans;
}
 
void solve() {
    string s, t;
    cin >> s >> t;
 
    for (auto i : match(s, t)) {
        cout << i + 1 << "\n";
    }
    for (auto x : prefixFunction(t)) {
        cout << x << " ";
    }
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 1e6 + 10, mod = 998244353;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<string> vec(n);
    int id = -1, len = 1e9;
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
        if (vec[i].size() < len) {
            id = i;
            len = vec[i].size();
        }
    }

    for (auto i = 0; i < vec.size() - 1; i++) {
        if (vec[i].size() != len) continue;
        if (vec[i] == vec[id]) continue;
        for (int i = 0; i < n; i++) {
            cout << 0 << '\n';
        }
        return 0;
    }

    string &t = vec[id];
    vector<int> nex(t.size());

    for (int i = 1; i < t.size(); i++) {
        int j = nex[i - 1];
        while (j && t[i] != t[j]) j = nex[j - 1];
        if (t[i] == t[j]) j++;
        nex[i] = j;
    }

    function<int(string &)> match = [&](string &s) -> int {
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i++) {
            while (j && s[i] != t[j]) j = nex[j - 1];
            if (s[i] == t[j]) j++;
            if (j == t.size()) {
                cnt++;
                j = nex[j - 1];
            }
        }
        return cnt;
    };

    ll ans = 1;

    for (auto &s : vec) {
        ans = ans * match(s) % mod;
    }

    for (auto &s : vec) {
        cout << (s.size() == len ? ans : 0) << '\n';
    }

    return 0;
}

Hash

多项式hash, 将字符串看作某个进制Base下的数字串

优点:一一对应,不会起冲突

缺点:值域过大

措施:模哈

生日悖论

自然溢出: ULL

优秀的Hash模数是质数,
选合数和话会出现零点问题等于选了很多的小质数,
1e9-1e10之间的质数,不要太大,乘法会溢出,

最保险的多模:

字串Hash,要用到前缀

#include <bits/stdc++.h>

#define ios cin.tie(nullptr)->sync_with_stdio(false)
#define endl '\n'

using namespace std;
using i64 = long long;

template <class T, const T P = 0> struct ModInt {
    static T _Mod;
    constexpr static T getMod() { return P > 0 ? P : _Mod; }
    constexpr static void setMod(T Mod) { _Mod = Mod; }
    constexpr T norm(T val) const { return val < 0 ? val += getMod() : val >= getMod() ? val -= getMod() : val; }

    T _val;
    constexpr ModInt() : ModInt(0) {}
    constexpr ModInt(T val) : _val(norm(val % getMod())) {}
    constexpr ModInt &operator=(T rhs) & { return *this = ModInt(rhs); }

    explicit constexpr operator T() const { return _val; }
    constexpr T val() const { return _val; }
    constexpr ModInt operator-() const { return ModInt(norm(getMod() - _val)); }

    constexpr ModInt power(ModInt x, i64 n) const {
        ModInt res = 1;
        for (; n; x *= x, n /= 2) {
            if (n % 2) res *= x;
        }
        return res;
    }
    constexpr ModInt inv() const {
        assert(_val != 0);
        return power(*this, getMod() - 2);
    }

    constexpr ModInt &operator+=(ModInt rhs) & { return _val = norm(_val + rhs.val()), *this; }
    constexpr ModInt &operator-=(ModInt rhs) & { return _val = norm(_val - rhs.val()), *this; }
    constexpr ModInt &operator*=(ModInt rhs) & { return _val = 1LL * _val * rhs.val() % getMod(), *this; }
    constexpr ModInt &operator/=(ModInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr ModInt operator+(ModInt lhs, ModInt rhs) { return lhs += rhs; }
    friend constexpr ModInt operator-(ModInt lhs, ModInt rhs) { return lhs -= rhs; }
    friend constexpr ModInt operator*(ModInt lhs, ModInt rhs) { return lhs *= rhs; }
    friend constexpr ModInt operator/(ModInt lhs, ModInt rhs) { return lhs /= rhs; }

    friend constexpr bool operator<(ModInt lhs, ModInt rhs) { return lhs.val() < rhs.val(); }
    friend constexpr bool operator==(ModInt lhs, ModInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(ModInt lhs, ModInt rhs) { return lhs.val() != rhs.val(); }

    friend istream &operator>>(istream &is, ModInt &x) {
        i64 val;
        return is >> val, x = ModInt(val), is;
    }
    friend ostream &operator<<(ostream &os, ModInt x) { return os << x.val(); }
};

template <class T, const T P> T ModInt<T, P>::_Mod;
using MInt = ModInt<int, int(1E9) + 7>;

struct String : public string {
    char &operator[](int pos) { return string::operator[](pos - 1); }
    const char &operator[](int pos) const { return string::operator[](pos - 1); }
};

template <class T1, class T2> struct ModPair : public pair<T1, T2> {
    constexpr ModPair() : pair<T1, T2>() {}
    constexpr ModPair(T1 first, T2 second) : pair<T1, T2>(first, second) {}
    friend constexpr ModPair operator+(ModPair lhs, const ModPair rhs) {
        return lhs.first += rhs.first, lhs.second += rhs.second, lhs;
    }
    friend constexpr ModPair operator-(ModPair lhs, const ModPair rhs) {
        return lhs.first -= rhs.first, lhs.second -= rhs.second, lhs;
    }
    friend constexpr ModPair operator*(ModPair lhs, const ModPair rhs) {
        return lhs.first *= rhs.first, lhs.second *= rhs.second, lhs;
    }
};

struct Hash {
    constexpr static int _Mod1 = 1E9 + 7, _Mod2 = 1E9 + 9;
    using HashInt1 = ModInt<int, _Mod1>;
    using HashInt2 = ModInt<int, _Mod2>;
    using HashPair = ModPair<HashInt1, HashInt2>;
    constexpr static HashPair _Base = HashPair(HashInt1(137), HashInt2(139));

    bool _rev;
    vector<HashPair> _code, _base;
    Hash(String &s, bool rev = false) : _rev(rev), _code(s.size() + 2), _base(s.size() + 2) { init(s); }
    void init(String &s) {
        if (_rev) {
            for (int i = s.size(); i >= 1; i--) _code[i] = _code[i + 1] * _Base + HashPair(s[i], s[i]);
        } else {
            for (int i = 1; i <= s.size(); i++) _code[i] = _code[i - 1] * _Base + HashPair(s[i], s[i]);
        }
        _base[0] = HashPair(1, 1);
        for (int i = 1; i <= s.size(); i++) _base[i] = _base[i - 1] * _Base;
    }

    HashPair query(int l, int r) const {
        if (_rev) return _code[l] - _code[r + 1] * _base[r - l + 1];
        else return _code[r] - _code[l - 1] * _base[r - l + 1];
    }
};

void solve() {
    int n;
    cin >> n;

    String a, b;
    cin >> a >> b;

    n = n * 2 + 1, a += a + '|', b += b + '|';
    for (int i = n - 1; i >= 1; i -= 2) {
        a[i] = a[i / 2], b[i] = b[i / 2];
        a[i - 1] = b[i - 1] = '|';
    }

    int ans = 1;
    Hash forA(a), backA(a, true), forB(b), backB(b, true);
    auto check = [&](Hash &h1, Hash &h2, int l1, int r1, int l2, int r2) {
        return h1.query(l1, r1) == h2.query(l2, r2);
    };
    for (int p = 1; p <= n; p++) {
        int l1 = 0, r1 = min(p - 1, n - p);
        while (l1 < r1) {
            int m = (l1 + r1 + 1) / 2;
            if (check(forA, backA, p - m, p - 1, p + 1, p + m)) l1 = m;
            else r1 = m - 1;
        }
        ans = max(ans, l1);

        int i = p - l1, j = p + l1 - 2;
        int l2 = 0, r2 = min(i - 1, n - j);
        while (l2 < r2) {
            int m = (l2 + r2 + 1) / 2;
            if (check(forA, backB, i - m, i - 1, j + 1, j + m)) l2 = m;
            else r2 = m - 1;
        }
        ans = max(ans, l1 + l2);
    }
    for (int p = 1; p <= n; p++) {
        int l1 = 0, r1 = min(p - 1, n - p);
        while (l1 < r1) {
            int m = (l1 + r1 + 1) / 2;
            if (check(forB, backB, p - m, p - 1, p + 1, p + m)) l1 = m;
            else r1 = m - 1;
        }
        ans = max(ans, l1);

        int j = p - l1 + 2, k = p + l1;
        int l2 = 0, r2 = min(j - 1, n - k);
        while (l2 < r2) {
            int m = (l2 + r2 + 1) / 2;
            if (check(forA, backB, j - m, j - 1, k + 1, k + m)) l2 = m;
            else r2 = m - 1;
        }
        ans = max(ans, l1 + l2);
    }
    cout << ans << endl;
}

int main() {
    ios;
    int T = 1;
    while (T--) solve();
    return 0;
}

贴了个板子

Trie

字符串匹配,感觉01Trie会更长用一点

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
 
struct Trie {
    static constexpr int ALPHA = 26;
    struct Node {
        int cnt;
        bool ended;
        array<int, ALPHA> next;
        Node() : cnt{0}, ended{false}, next{} {}
    };
    vector<Node> t;
    Trie() { init(); }
    void init() {
        t.assign(2, {});
        t[0].next.fill(1);
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int add(const vector<int> &a) {
        int p = 1;
        for (auto x : a) {
            if (t[p].next[x] == 0) {
                t[p].next[x] = newNode();
            }
            p = t[p].next[x];
            t[p].cnt++;
        }
        t[p].ended = true;
        return p;
    }
    int add(const string &s, char offset = 'a') {
        vector<int> a;
        for (auto c : s) {
            a.push_back(c - offset);
        }
        return add(a);
    }
    int cnt(int p) { return t[p].cnt; }
    bool ended(int p) { return t[p].ended; }
    int next(int p, int x) { return t[p].next[x]; }
    int next(int p, char c, char offset = 'a') { return next(p, c - offset); }
    int size() { return t.size(); }
};
 
void solve() {
    int n;
    cin >> n;
 
    Trie t;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        t.add(s[i]);
    }
 
    auto check = [&](int i) {
        vector<int> deg(26);
        vector<vector<int>> adj(26);
        for (int p = 1; auto c : s[i]) {
            if (t.ended(p)) {
                return false;
            }
            for (int x = 0; x < 26; x++) {
                if (x == c - 'a' || !t.next(p, x)) {
                    continue;
                }
                adj[c - 'a'].push_back(x);
                deg[x]++;
            }
            p = t.next(p, c);
        }
        queue<int> que;
        for (int i = 0; i < 26; i++) {
            if (deg[i] == 0) {
                que.push(i);
            }
        }
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (auto y : adj[x]) {
                if (--deg[y] == 0) {
                    que.push(y);
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (deg[i] != 0) {
                return false;
            }
        }
        return true;
    };
 
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (check(i)) {
            ans.push_back(i);
        }
    }
 
    cout << ans.size() << "\n";
    for (auto i : ans) {
        cout << s[i] << "\n";
    }
}

01Trie

struct Trie {
    static constexpr int ALPHA = 2;
    struct Node {
        int cnt;
        array<int, ALPHA> next;
        Node() : cnt{0}, next{} {}
    };
    vector<Node> t;
    Trie() { init(); }
    void init() {
        t.assign(2, {});
        t[0].next.fill(1);
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int add(const vector<int> &a) {
        int p = 1;
        for (auto x : a) {
            if (t[p].next[x] == 0) {
                t[p].next[x] = newNode();
            }
            p = t[p].next[x];
            t[p].cnt++;
        }
        return p;
    }
    int add(int v, int width = 31) {
        vector<int> a;
        for (int i = width - 1; i >= 0; i--) {
            a.push_back(v >> i & 1);
        }
        return add(a);
    }
    int cnt(int p) { return t[p].cnt; }
    int next(int p, int x) { return t[p].next[x]; }
    int next(int p, char c, char offset = 'a') { return next(p, c - offset); }
    int size() { return t.size(); }
};
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    Trie t;
    auto query = [&](int v) {
        int res = 0;
        for (int i = 30, p = 1; i >= 0; i--) {
            int x = v >> i & 1;
            if (t.next(p, x ^ 1) != 0) {
                x ^= 1;
                res |= 1 << i;
            }
            p = t.next(p, x);
        }
        return res;
    };
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        t.add(a[i]);
        ans = max(ans, query(a[i]));
    }
    cout << ans << "\n";
}

ACAM

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模匹配等任务。
注意ACAM是离线算法,不可以动态进行操作

简单来说，建立一个 AC 自动机有两个步骤:

1.基础的 Trie 结构：将所有的模式串构成一棵 Trie。
2.KMP 的思想：对 Trie 树上所有的结点构造失配指针。

建立完毕后，就可以利用它进行多模式匹配。

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) void()
#endif

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;

struct AhoCorasick {
    static constexpr int SIZE = 26;
    struct Node {
        int len, link;
        array<int, SIZE> next;
        Node() : len{0}, link{0}, next{} {}
    };
    vector<Node> t;
    AhoCorasick() { init(); }
    void init() { t.assign(1, {}); }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int add(const vector<int> &a) {
        int p = 0;
        for (auto x : a) {
            if (t[p].next[x] == 0) {
                t[p].next[x] = newNode();
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];
        }
        return p;
    }
    int add(const string &s, char offset = 'a') {
        vector<int> a;
        for (auto c : s) {
            a.push_back(c - offset);
        }
        return add(a);
    }
    void work() {
        queue<int> que;
        for (int i = 0; i < SIZE; i++) {
            if (t[0].next[i] != 0) {
                que.push(t[0].next[i]);
            }
        }
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            for (int i = 0; i < SIZE; i++) {
                if (t[x].next[i] == 0) {
                    t[x].next[i] = t[t[x].link].next[i];
                } else {
                    t[t[x].next[i]].link = t[t[x].link].next[i];
                    que.push(t[x].next[i]);
                }
            }
        }
    }
    int len(int p) { return t[p].len; }
    int link(int p) { return t[p].link; }
    int next(int p, int x) { return t[p].next[x]; }
    int next(int p, char c, char offset = 'a') { return next(p, c - offset); }
    int size() { return t.size(); }
} ac;

void solve() {
    int n;
    cin >> n;

    ac.init();
    vector<int> end(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        end[i] = ac.add(s);
    }
    ac.work();

    string s;
    cin >> s;

    vector<int> f(ac.size());
    for (int p = 0; auto c : s) {
        p = ac.next(p, c);
        f[p]++;
    }

    vector<vector<int>> adj(ac.size());
    for (int i = 1; i < ac.size(); i++) {
        adj[ac.link(i)].push_back(i);
    }

    auto dfs = [&](auto &&self, int x) -> void {
        for (auto y : adj[x]) {
            self(self, y);
            f[x] += f[y];
        }
    };
    dfs(dfs, 0);

    for (int i = 0; i < n; i++) {
        cout << f[end[i]] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(16);

    int t = 1;

    while (t--) {
        solve();
    }

    return 0;
}

优化版的,懒得去学优化了