字符串杂题

P3449 [POI 2006] PAL-Palindromes

给定 \(n\) 个回文串，随后将这些字符串两两组合，拼接成 \(n^2\) 个新串（区分顺序，可以自己和自己组合）。问这些新串中有多少个是回文的。

\(\sum |s_i|\le 2\times 10^6\)

先特判掉自己和自己拼接的情况。发现一个较长的串 \(a\) 可以匹配一个较短的串 \(b\) 当且仅当 \(a\) 可以拆分成一个任意回文串和 \(b\) 的拼接。我们枚举断点，判断左侧是否是回文串，然后把右侧的哈希值扔进哈希表里即可。

P3065 [USACO12DEC] First! G

给定 \(n\) 个两两不同，由小写字母组成的字符串，问有多少个串可以通过任意排列字母表的顺序变成 \(n\) 个串中字典序最小的。

\(n\le 3\times 10^4,\ \sum|s_i|\le 3\times 10^5\)

先建出字典树，然后依次钦定每个串为字典序最小的，可以建出一张 \(26\) 个点的有向图，然后判环即可。

时间复杂度 \(O\bigl(n\Sigma^2+\Sigma\times (\sum|s_i|)\bigr)\)

P3435 [POI 2006] OKR-Periods of Words

称 \(Q\) 是 \(A\) 的“2-周期”当且仅当 \(Q\) 是 \(A\) 的非空真前缀并且 \(A\) 是 \(QQ\) 的前缀。

给定字符串 \(A\)，请你求出它所有前缀的最大“2-周期”长度之和。若不存在则贡献为 \(0\)。

\(|A|\le 10^6\)

不难发现，若存在“2-周期”，那么最长的“2-周期”就是字符串的最长周期。根据周期和 border 的一一对应关系，最长周期就是最短 border。找到最长周期后，容易判断是否是“2-周期”。

现在问题转化为求每个前缀的最短 border，可以理解为求每个前缀在 fail 树上的根（不考虑空节点）。发现容易使用路径压缩（记忆化搜索）处理。

P6727 [COCI 2015/2016 #5] OOP

给定 \(n\) 个单词和 \(q\) 个模板，一个模板由一个 * 和一些小写字母组成。一个模板覆盖了一个单词当且仅当将 * 替换为某个字符串（可以为空）后，模板和单词能够完全重合。对于每个模板，求出它能够覆盖多少个单词。

\(n,q\le 3\times 10^5\)，读入的总字符数不超过 \(3\times 10^6\)

发现前缀和后缀的限制容易转换为字典树上的 dfn 序，然而还有长度的限制，因为前后缀不能重叠。这样问题就转化为一个三维偏序问题。

我们有更优的做法。先将所有单词正序建出一棵字典树，考虑一次询问 \((a,b)\)（\(a\) 表示前缀，\(b\) 表示后缀），先跳到 \(a\) 所在的节点 \(x\)，问题转化为求 \(x\) 子树内有多少个字符串包含后缀 \(b\)。考虑把每个单词的每个后缀，算出哈希值后挂在后缀开头对应的位置上。这样上面的询问操作就等价于一次子树查询，查询子树内有多少个哈希值匹配的后缀。容易使用扫描线和哈希表维护。

在 \(\sum|s_i|\) 有保证时，前缀、后缀关系可以直接用哈希进行处理，而不使用字典树 dfn 序。

代码

#include<iostream>
#include<vector>
#include<cassert>
#include<cstring>
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 10;
const int S = 3e6 + 10;

struct myPair {
    ull val;
    int id, w;
};

struct hash_table {
    static const int MOD = 3000017;
    struct Node {
        ull key;
        int v, next;
    } pool[2 * S];
    int nn, head[MOD];
    inline hash_table() { nn = 0; memset(head, 0, sizeof(head)); }
    inline int & insert(ull key) {
        pool[++nn] = {key, 0, head[key % MOD]};
        head[key % MOD] = nn;
        return pool[nn].v;
    }
    inline int & operator[](ull key) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) return pool[i].v;
        }
        return insert(key);
    }
} mp;

int n, nq;
int ans[N];

int chd[S][26], nn = 1;
int dfn[S], id[S], sz[S], dt;

vector<ull> a[S];
vector<myPair> q[S];

void insert(const string &s) {
    int cur = 1;
    static ull hsh[S];
    hsh[s.size()] = 0;
    for(int i = s.size() - 1; i >= 0; i--) {
        hsh[i] = hsh[i + 1] * 29 + s[i] - 'a' + 1;
    }
    for(int i = 0; i < s.size(); i++) {
        if(!chd[cur][s[i] - 'a']) chd[cur][s[i] - 'a'] = ++nn;
        a[cur].push_back(hsh[i]);
        cur = chd[cur][s[i] - 'a'];
    }
    a[cur].push_back(0);
}

int run(const string &s) {
    int cur = 1;
    for(int i = 0; i < s.size(); i++) {
        if(!chd[cur][s[i] - 'a']) return 0;
        cur = chd[cur][s[i] - 'a'];
    }
    return cur;
}

void dfs(int u) {
    dfn[u] = ++dt;
    id[dt] = u;
    sz[u] = 1;
    for(int i = 0; i < 26; i++) {
        int v = chd[u][i];
        if(!v) continue;
        dfs(v);
        sz[u] += sz[v];
    }
}

ull get_hsh(const string &s) {
    ull hsh = 0;
    for(int i = s.size() - 1; i >= 0; i--) hsh = hsh * 29 + s[i] - 'a' + 1;
    return hsh;
}

void add_query(int l, int r, ull hsh, int id) {
    q[l].push_back({hsh, id, -1});
    q[r].push_back({hsh, id, 1});
}

int main() {

    cin >> n >> nq;
    for(int i = 1; i <= n; i++) {
        static string s;
        cin >> s;
        insert(s);
    }

    dfs(1);

    for(int i = 1; i <= nq; i++) {
        static string s, a, b;
        cin >> s;
        a.clear(); b.clear();
        for(int i = 0, j = 0; i < s.size(); i++) {
            if(s[i] == '*') { j = 1; continue; }
            if(j) b.push_back(s[i]);
            else a.push_back(s[i]);
        }
        int p = run(a);
        if(p) add_query(id[dfn[p] - 1], id[dfn[p] + sz[p] - 1], get_hsh(b), i);
    }

    for(int i = 1; i <= nn; i++) {
        int p = id[i];
        for(ull x : a[p]) {
            ++mp[x];
        }
        for(myPair &o : q[p]) {
            ans[o.id] += mp[o.val] * o.w;
        }
    }

    for(int i = 1; i <= nq; i++) cout << ans[i] << '\n';

    return 0;
}

P4696 [CEOI 2011] Matching

称两个数字序列匹配，当且仅当每个位置数字的排名相等。保证不存在重复数字。

给定一个长度为 \(n\) 的序列 \(a\) 和长度为 \(m\) 的序列 \(b\)，保证 \(n\le m\)，问 \(a\) 在 \(b\) 中出现了多少次。

\(2\le n\le m\le 10^6\)

题目中匹配的定义显然具有传递性，因此可以使用 KMP 求解。向后匹配一个字符的方法就是：查询这个位置在两个序列中的排名，检查是否相等。

使用树状数组维护排名。由于 KMP 保证每个字符均摊处理 \(O(1)\) 次，跳 fail 的时候暴力将区间中的数字一个一个在树状数组中删去即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;

int n, m;
int s[N], t[N];

void inv() {
    static int tmp[N];
    for(int i = 1; i <= n; i++) tmp[i] = t[i];
    for(int i = 1; i <= n; i++) t[tmp[i]] = i;
}

void lisanhua() {
    static int num[N], nn;
    for(int i = 1; i <= m; i++) num[++nn] = s[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= m; i++) s[i] = lower_bound(num + 1, num + 1 + nn, s[i]) - num;
}

namespace BIT {
    int sum[N];
    inline void clear() {
        for(int i = 0; i <= m + 5; i++) sum[i] = 0;
    }
    inline void add(int p) {
        // cout << "add: " << p << '\n';
        for(int i = p; i <= m; i += i & -i) ++sum[i];
    }
    inline void erase(int p) {
        // cout << "erase: " << p << '\n';
        for(int i = p; i <= m; i += i & -i) --sum[i];
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p - 1; i > 0; i -= i & -i) res += sum[i];
        return res + 1;
    }
}

int b[N], nxt[N];
int ans[N], cnt;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> t[i];
    for(int i = 1; i <= m; i++) cin >> s[i];

    inv();
    lisanhua();

    for(int i = 1; i <= n; i++) {
        b[i] = BIT::query(t[i]);
        BIT::add(t[i]);
    }
    BIT::clear();

    // cout << endl;

    // for(int i = 1; i <= n; i++) cout << t[i] << ' ';
    // cout << '\n';

    for(int i = 2, j = 0; i <= n; i++) {
        while(j && BIT::query(t[i]) != b[j + 1]) {
            // if(t[i] == 5) cout << "test: " << BIT::query(t[i]) << ' ' << j << ' ' << b[j + 1] << '\n';
            for(int k = i - j; k < i - nxt[j]; k++) BIT::erase(t[k]);
            j = nxt[j];
        }
        if(BIT::query(t[i]) == b[j + 1]) {
            BIT::add(t[i]);
            ++j;
        }
        nxt[i] = j;
    }
    BIT::clear();

    for(int i = 1, j = 0; i <= m; i++) {
        while(j && BIT::query(s[i]) != b[j + 1]) {
            for(int k = i - j; k < i - nxt[j]; k++) BIT::erase(s[k]);
            j = nxt[j];
        }
        if(BIT::query(s[i]) == b[j + 1]) {
            BIT::add(s[i]);
            ++j;
        }
        if(j == n) {
            ans[++cnt] = i - n + 1;
            for(int k = i - j + 1; k < i - nxt[j] + 1; k++) BIT::erase(s[k]);
            j = nxt[j];
        }
    }

    cout << cnt << '\n';
    for(int i = 1; i <= cnt; i++) cout << ans[i] << ' ';
    cout << '\n';

    return 0;
}

C23155 串论

称两个数字序列匹配，当且仅当每个位置数字的排名相等。可能存在重复数字。

给定一个长度为 \(n\) 的序列 \(a\) 和长度为 \(m\) 的序列 \(b\)，求 \(b\) 的每个后缀与 \(a\) 的最长公共前缀。

\(n+m\le 5\times 10^5\)

由于匹配的传递性以及子段匹配的性质，可以使用 Z 函数求解。仍然使用树状数组维护排名。发现扩展时只会匹配 \(k+z[k]\) 位置的字符，因此需要用树状数组维护的始终是一段区间 \([i,k+z[k])\)。区间两端点都单调不降，因此均摊线性，时间复杂度 \(O(n\log n)\)。

对于相等数字，记一个桶即可。也可以开第二个树状数组，二者等价。

代码

#include<iostream>
using namespace std;
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
int a[2 * N];
int rk[2 * N], eq[2 * N];

int z[2 * N];

int inBIT[2 * N];

namespace BIT {
    int sum[N];
    inline void clear() {
        for(int i = 0; i < N; i++) sum[i] = 0;
    }
    inline void add(int p) {
        for(int i = p; i < N; i += i & -i) ++sum[i];
    }
    inline void erase(int p) {
        for(int i = p; i < N; i += i & -i) --sum[i];
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= i & -i) res += sum[i];
        return res;
    }
}

#define FIO

int main() {

    #ifdef FIO
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    #endif

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = n + 1; i <= n + m; i++) cin >> a[i];

    for(int i = 1; i <= n; i++) {
        rk[i] = BIT::query(a[i] - 1);
        eq[i] = BIT::query(a[i]);
        BIT::add(a[i]);
    }
    BIT::clear();

    int l = 2, r = 0, k = 0;
    for(int i = 2, j = 0; i <= n; i++) {
        if(l < i) BIT::erase(a[l++]);
        if(i <= r) z[i] = min(z[k] + k - i, z[i - k + 1]);
        if(i + z[i] > r) {
            while(i + z[i] <= n && BIT::query(a[i + z[i]] - 1) == rk[z[i] + 1] && BIT::query(a[i + z[i]]) == eq[z[i] + 1]) {
                BIT::add(a[i + z[i]]);
                ++z[i];
            }
            r = i + z[i] - 1;
            k = i;
        }
    }

    BIT::clear();

    k = 0;
    l = n + 1;
    r = n;
    for(int i = n + 1, j = 0; i <= n + m; i++) {
        if(l < i) BIT::erase(a[l++]);
        if(i <= r) z[i] = min(z[k] + k - i, z[i - k + 1]);
        if(i + z[i] > r) {
            while(i + z[i] <= n + m && z[i] < n && BIT::query(a[i + z[i]] - 1) == rk[z[i] + 1] && BIT::query(a[i + z[i]]) == eq[z[i] + 1]) {
                BIT::add(a[i + z[i]]);
                ++z[i];
            }
            r = i + z[i] - 1;
            k = i;
        }
    }

    for(int i = n + 1; i <= n + m; i++) cout << z[i] << ' ';
    cout << '\n';

    return 0;
}