【题解】2018-ICPC-南京-M-Mediocre String Problem

Posted on In Disqus:

题目

https://codeforces.com/gym/101981/problem/M

题意

给出两个字符串 \(s\) 和 \(t\)，要求从 \(s\) 切出一段非空子串，\(t\) 中切出一段非空前缀，且 \(s\) 的比 \(t\) 的长，使得拼接起来是个回文串。

题解

  • \(s\) 中切出来的是 \(t\) 中的某个子串的反串再接上一段回文。
  • 将 \(s\) 翻转后可以方便的求出 \(s\) 中每个位置开始的回文串个数（回文树），以及每个位置开始向前能匹配的 \(t\) 的前缀的长度（Z Algorithm），错一位相乘累加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------
const int N = 2E6 + 100;

namespace pam {
    int t[N][26], fa[N], len[N], rs[N], cnt[N], num[N];
    int sz, n, last;
    int _new(int l) {
        memset(t[sz], 0, sizeof t[0]);
        len[sz] = l; cnt[sz] = num[sz] = 0;
        return sz++;
    }
    void init() {
        rs[n = sz = 0] = -1;
        last = _new(0);
        fa[last] = _new(-1);
    }
    int get_fa(int x) {
        while (rs[n - 1 - len[x]] != rs[n]) x = fa[x];
        return x;
    }
    void ins(int ch) {
        rs[++n] = ch;
        int p = get_fa(last);
        if (!t[p][ch]) {
            int np = _new(len[p] + 2);
            num[np] = num[fa[np] = t[get_fa(fa[p])][ch]] + 1;
            t[p][ch] = np;
        }
        ++cnt[last = t[p][ch]];
    }
}

void get_z(int a[], char s[], int n) {
    int l = 0, r = 0; a[0] = n;
    FOR (i, 1, n) {
        a[i] = i > r ? 0 : min(r - i + 1, a[i - l]);
        while (i + a[i] < n && s[a[i]] == s[i + a[i]]) ++a[i];
        if (i + a[i] - 1 > r) { l = i; r = i + a[i] - 1; }
    }
}

char s[N], t[N];
int z[N], c[N];
int main() {
    scanf("%s%s", s, t);
    int n = strlen(s), m = strlen(t);
    reverse(s, s + n);
    t[m] = '#'; FOR (i, 0, n) t[m + 1 + i] = s[i];
    get_z(z, t, n + m + 1);
    pam::init();
    FOR (i, 0, n) {
        pam::ins(s[i] - 'a');
        c[i] = pam::num[pam::last];
    }
    LL ans = 0;
    FOR (i, 0, n - 1)
        ans += c[i] * 1LL * z[m + 1 + i + 1];
    cout << ans << endl;
}