Skip to content

字符串训练

update1：期末周闲来无事，找了四道字符串写了下。

CF1923F

整道题最难的点在于对贪心的分析。

首先有一个很明显的贪心，那就是让二进制下的有效位数尽可能地少，这启发我们去关注距离最远的两个 1 的距离，注意到操作 2 不会改变距离最远的两个 1 的距离。由此可以得出：

操作 2 不会超过 1 次。

证明很简单，因为我把多出来的次数用来减少距离最远的两个 1 的距离会更好。 那么只需要分是否有操作 2 讨论取最小即可。

首先，我们有如下显然结论：

对于没有操作 2 的情况，不断把最靠前的 1 和最靠后的 0 交换位置。

对于存在操作 2 的情况，我们最后执行操作 2 会更好。

然后，对于存在操作 2 的情况，我们可以先二分求出最小的最远的两个 1 的距离，因为前后导零都没意义，这种情况显然比其他更优秀。每次二分都尝试 \(O(n)\) 个区间，区间合法等价于 区间外 1 的个数不超过 \(k\) ，这部分复杂度是 \(O(nlogn)\) 。

然后我们需要最小长度的合法区间中从中找到最优解，对于一个合法区间，我们肯定会把外面的 1 往较小权值的位置（也就是越靠前的位置，因为有操作 2 的反转）放，所以最后的答案就是一段连续的 1 加 一段原串。 所以我们只需要把原串反转一下，找到字典序最小的后缀作为区间左端点即可。

这样做可行是因为所有合法答案最终必有内部 0 的个数相同，1 的个数也相同，所以我们如果考虑比较两个答案，要么在原串部分就比较结束，要么两者就是等价的。因此直接比较后缀的字典序是可行的。

代码实现上，我是对每个右端点二分最小长度，基本思路还是一样的。然后比较后缀的字典序通过后缀数组实现。时间复杂度 \(O(nlogn)\) ，空间复杂度 \(O(nlogn)\) 。

代码 
  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>

using namespace std;


const int N = 5e5 + 10, mod = 1e9 + 7;

struct ST {
    int logn[N], mi[21][N];
    void init(int* a, int n) {
        for (int i = 2; i <= n; i++) logn[i] = logn[i >> 1] + 1;
        for (int i = 1; i <= n; i++) mi[0][i] = a[i];
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                mi[j][i] = min(mi[j - 1][i], mi[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    int rmq(int l, int r) {
        int k = logn[r - l + 1];
        return min(mi[k][l], mi[k][r - (1 << k) + 1]);
    }
};
struct SA {
    int id[N], c[N], sa[N], rk[N], ht[N];
    // sa[i] 表示排名为 i 的后缀 s[sa[i], n] 的原始位置 (sa[rk[i]] = i)
    // rk[i] 表示原始后缀 s[i, n] 在后缀数组中的排名 rk (rk[sa[i]] = i)
    // ht[i] 表示排名为 i 的后缀 s[sa[i], n] 与排名为 i-1 的后缀 s[sa[i-1], n] 的 LCP
    ST st;
    template <typename T>
    void getsa(T s, int n, int m = 100) {
        for (int i = 1; i <= n; ++i) rk[i] = s[i] - '0' + 1, id[i] = i;
        for (int i = 0; i <= m; ++i) c[i] = 0;
        for (int i = 1; i <= n; ++i) c[rk[i]]++;
        for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
        for (int i = n; i >= 1; --i) sa[c[rk[id[i]]]--] = id[i];
        for (int w = 1, p = 0; p < n; m = p, w <<= 1) {
            p = 0;
            for (int i = 1; i <= w; ++i) id[++p] = n - w + i;
            for (int i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;
            for (int i = 0; i <= m; ++i) c[i] = 0;
            for (int i = 1; i <= n; ++i) c[rk[i]]++;
            for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
            for (int i = n; i >= 1; --i) sa[c[rk[id[i]]]--] = id[i];
            for (int i = 1; i <= n; ++i) id[i] = rk[i];
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; ++i)
                rk[sa[i]] = (id[sa[i - 1]] == id[sa[i]] && id[sa[i - 1] + w] == id[sa[i] + w]) ? p : ++p;
        }
        for (int i = 1, k = 0; i <= n; ++i) {
            if (rk[i] == 0) continue;
            if (k) --k;
            while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
            ht[rk[i]] = k;
        }
        for (int i = 1; i <= n; ++i) id[i] = 0;
    }
    void debug(int n) {
        for (int i = 1; i <= n; ++i) {
            cout << "sa[" << i << "]=" << sa[i] << " rk[" << i << "]=" << rk[i] << " ht[" << i << "]=" << ht[i] << "\n";
        }
    }
    // 字符串 s 是以 1 下标开头的字符串，长度为 n
    template <typename T>
    void init(T s, int n, int m = 100) {
        getsa(s, n, m); // 求 sa，rk，height
        st.init(ht, n); // height 初始化 st 表
    }
    // 求任意两个后缀的 LCP：LCP(s[a, n], s[b, n])
    // LCP(LCP(s[l], s[l + 1]) ... LCP(s[r - 1], s[r]))
    // min(ht[l + 1] ... ht[r]) = rmq(l + 1, r)
    int get_lcp(int a, int b) {
        int l = rk[a], r = rk[b];
        if (l > r) swap(l, r);
        return st.rmq(l + 1, r);
    }
} sa;
int n, k, cnt[N];
char s[N], t[N];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k >> (s + 1);
    vector<int>v(1, 0);
    int m = k, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0')v.push_back(i);
        else sum++;

    }
    memcpy(t, s, sizeof s);
    for (int i = 1; i < v.back() && m; i++)
    {
        if (s[i] == '1') {
            swap(t[i], t[v.back()]);
            v.pop_back();
            m--;
        }
    }

    k--;
    for (int i = 1, j = n; i < j; i++, j--)swap(s[i], s[j]);
    for (int i = 1; i <= n; i++)cnt[i] = cnt[i - 1] + s[i] - '0';

    sa.init(s, n);
    v.clear();
    int res = n + 1;

    for (int i = 1; i + sum - 1 <= n && cnt[i - 1] <= k; i++)
    {
        int l = sum , r = n - i + 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (k >= cnt[i - 1] + cnt[n] - cnt[i + mid - 1])r = mid;
            else l = mid + 1;
        }

        if (r < res) {
            res = r;
            v.clear();
            v.push_back(i);
        }
        else if (r == res)v.push_back(i);
    }
    sort(v.begin(), v.end(), [](int a, int b) {
        return sa.rk[a] < sa.rk[b];
    });
    int i = v[0], j = 1;
    while (t[j] == '0')j++;

    for (int pos = i + res - 1; pos >= i && k; pos--) {
        if (s[pos] == '0')s[pos] = '1', k--;
    }
    bool ok = 0;
    if (res != n - j + 1) ok = (res < n - j + 1);
    else {
        while (s[i] == t[j] && j <= n) {

            i++, j++;
        }
        ok = (s[i] < t[j]);
    }

    j = 1, i = v[0];
    while (t[j] == '0')j++;
    long long ans = 0;
    if (ok)for (int k = i; k <= i + res - 1; k++)ans = (ans * 2 + s[k] - '0') % mod;
    else for (int k = j; k <= n; k++)ans = (ans * 2 + t[k] - '0') % mod;
    cout << ans << '\n';
    return 0;
}

CF1913F

首先注意到所有的修改方案只有 \(25n\) 种，我们可以暴力比较每种方案，那么关键就是求出每种方案回文子串数量的改变。

将修改第 \(i\) 个字符的操作看作先替换为一个特殊字符，然后再替换为我们想要的字符，我们关心这两个过程回文子串数量变化量的差值。

第一个过程会丢失一部分回文子串，也就是包括第 \(i\) 个字符的回文子串数量 \(cnt[i]\) 。我们按照回文中心去统计， 在跑马拉车算法的过程我们可以求出每个回文中心的回文半径，注意这个回文中心的回文串对回文半径内部的点的 \(cnt[i]\) 的贡献是加上 2 个等差数列，可以通过二阶差分维护。

第二个过程新增的回文子串可以分为两类，一种是以自身为回文中心的，在马拉车算法的过程就可以顺便求出，当然如果你前面删子串时本身就没考虑这种那这里也就不用增加了。 另外一种就是在某个回文中心失配时对失配处字符的修改使之匹配成功，后续的匹配过程其实就是一个类似于求 lcp 的过程，我们对 原串 + 特殊字符 + 反串建后缀数组，然后就可以 \(O(nlogn)\) 预处理，\(O(1)\) 求出新增的匹配长度， 也就是这种修改对这个回文中心新增的回文子串数量。

注意最后找最小字典序的细节，具体可以分为 3 类：往小修改，不修改，原串。同时还要保证回文子串变化量最大。

代码 
  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
char s[N];
int n;
long long del[N], add[N][26];
struct ST {
    int logn[N], mi[21][N];
    void init(int* a, int n) {
        for (int i = 2; i <= n; i++) logn[i] = logn[i >> 1] + 1;
        for (int i = 1; i <= n; i++) mi[0][i] = a[i];
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                mi[j][i] = min(mi[j - 1][i], mi[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    int rmq(int l, int r) {
        int k = logn[r - l + 1];
        return min(mi[k][l], mi[k][r - (1 << k) + 1]);
    }
};
struct SA {
    int id[N], c[N], sa[N], rk[N], ht[N];
    // sa[i] 表示排名为 i 的后缀 s[sa[i], n] 的原始位置 (sa[rk[i]] = i)
    // rk[i] 表示原始后缀 s[i, n] 在后缀数组中的排名 rk (rk[sa[i]] = i)
    // ht[i] 表示排名为 i 的后缀 s[sa[i], n] 与排名为 i-1 的后缀 s[sa[i-1], n] 的 LCP
    ST st;
    template <typename T>
    void getsa(T s, int n, int m = 100) {
        for (int i = 1; i <= n; ++i) rk[i] = s[i] - '0' + 1, id[i] = i;
        for (int i = 0; i <= m; ++i) c[i] = 0;
        for (int i = 1; i <= n; ++i) c[rk[i]]++;
        for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
        for (int i = n; i >= 1; --i) sa[c[rk[id[i]]]--] = id[i];
        for (int w = 1, p = 0; p < n; m = p, w <<= 1) {
            p = 0;
            for (int i = 1; i <= w; ++i) id[++p] = n - w + i;
            for (int i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;
            for (int i = 0; i <= m; ++i) c[i] = 0;
            for (int i = 1; i <= n; ++i) c[rk[i]]++;
            for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
            for (int i = n; i >= 1; --i) sa[c[rk[id[i]]]--] = id[i];
            for (int i = 1; i <= n; ++i) id[i] = rk[i];
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; ++i)
                rk[sa[i]] = (id[sa[i - 1]] == id[sa[i]] && id[sa[i - 1] + w] == id[sa[i] + w]) ? p : ++p;
        }
        for (int i = 1, k = 0; i <= n; ++i) {
            if (rk[i] == 0) continue;
            if (k) --k;
            while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
            ht[rk[i]] = k;
        }
        for (int i = 1; i <= n; ++i) id[i] = 0;
    }
    void debug(int n) {
        for (int i = 1; i <= n; ++i) {
            cout << "sa[" << i << "]=" << sa[i] << " rk[" << i << "]=" << rk[i] << " ht[" << i << "]=" << ht[i] << "\n";
        }
    }
    // 字符串 s 是以 1 下标开头的字符串，长度为 n
    template <typename T>
    void init(T s, int n, int m = 100) {
        getsa(s, n, m); // 求 sa，rk，height
        st.init(ht, n); // height 初始化 st 表
    }
    // 求任意两个后缀的 LCP：LCP(s[a, n], s[b, n])
    // LCP(LCP(s[l], s[l + 1]) ... LCP(s[r - 1], s[r]))
    // min(ht[l + 1] ... ht[r]) = rmq(l + 1, r)
    int lcp(int a, int b) {
        if (a > b)swap(a, b);
        if (a == 0 || b == 2 * n + 2)return 0;
        int l = rk[a], r = rk[b];
        if (l > r) swap(l, r);
        return st.rmq(l + 1, r);
    }
} sa;

vector<int> manacher(string& s) {

    string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) r[i]++;

        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string t; cin >> n >> t;

    for (int i = 1; i <= n; i++)s[i] = s[2 * n + 2 - i] = t[i - 1];
    s[n + 1] = 'a' - 1;
    auto d = manacher(t);
    //cerr << s + 1 << endl;
    sa.init(s, 2 * n + 1);

    //#s[1]#s[2]
    for (int i = 0; i < d.size(); i++)
    {
        //右端点 (i+d[i]-1+1)/2
        //左端点 (i-d[i]+1)/2+1
        int l = (i - d[i] + 1) / 2 + 1, r = (i + d[i]) / 2;
        if (l > 1 && r < n) {
            int val = sa.lcp(r + 2, 2 * n - l + 4);
            add[l - 1][s[r + 1] - 'a'] += val + 1;
            add[r + 1][s[l - 1] - 'a'] += val + 1;
            //cout << l - 1 << ' ' << r + 1 << ' ' << val + 1 << endl;
        }
        if (l <= r) {

            del[l]++, del[(i + 1) / 2 + 1]--, del[i / 2 + 2]--, del[r + 2]++;
        }
    }

    for (int i = 1; i <= n; i++)del[i] += del[i - 1];
    for (int i = 1; i <= n; i++)del[i] += del[i - 1];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 26; j++)if (j != s[i] - 'a')add[i][j] += d[2 * i - 1] / 2;

    long long res = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            if (s[i] - 'a' == j)continue;
            res = max(res, add[i][j] - del[i]);
        }
    }

    vector<array<int, 3>>v;
    bool ok = 0;

    for (int i = 1; i <= n && !ok; i++)
    {
        for (int j = 0; j < s[i] - 'a' && !ok; j++)
        {
            if (res == add[i][j] - del[i]) {
                s[i] = char(j + 'a'), ok = 1;
            }
        }
    }
    ///cout << add[6]['y' - 'a'] << endl;
    ok |= (res == 0);
    for (int i = n; i && !ok; i--)
    {
        for (int j = s[i] - 'a' + 1; j < 26 && !ok; j++)
        {
            if (res == add[i][j] - del[i]) {
                s[i] = char(j + 'a'), ok = 1;
                break;
            }
        }
    }

    string st;
    for (int i = 1; i <= n; i++)st += s[i];
    d = manacher(st);
    long long sum = 0;
    for (int i = 0; i < d.size(); i++)
    {
        //右端点 (i+d[i]-1+1)/2
        //左端点 (i-d[i]+1)/2+1
        int len = d[i] - 1;
        sum += (len + 1) / 2;
    }

    cout << sum << '\n';
    for (int i = 1; i <= n; i++)cout << s[i];
    return 0;
}

CF1400F

打表发现题干定义的 \(x-prime\) 字符串，也就是非法子串数量不多，总长度不超过 \(1e4\) 。那就暴力搜出来所有非法子串。

禁止出现其实就是禁止成功匹配，那么我们很容易想到对所有非法子串建出 AC 自动机，同时给每个非法子串的终止结点打上标记。 匹配过程就是在 AC 自动机上转移，同时我们禁止走到标记点的子树内部。

考虑 \(dp[i][j]\) 表示从第 \(i+1\) 个字符开始，同时 AC 自动机上从 \(j\) 号点开始走完最少需要删除的字符。 \(j\) 为非法结点直接置为正无穷 ，反之才考虑转移。

转移的话可以考虑枚举我们走的下一个字符种类 \(c\) ，一个显然的贪心就是我们一定会选择走从 \(i+1\) 开始的第一个 \(c\) 字符，然后删除中间的部分，因为这样可以有更多的选择。

所以倒着做 \(DP\) ，同时用子序列自动机维护每个字符最先出现的位置即可。时间复杂度为 \(O(26cnt*len)\) ，\(cnt\) 为 AC 自动机结点个数，\(len\) 为原串长度。

代码 
  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e3 + 10;
int x;
char s[N];
int dp[N][N * 10];

//by jiangly
//1 号结点为空串 0号结点无意义
struct ACAM {
    static constexpr int M = 10;
    struct Node {
        int len;
        int link;
        array<int, M> next;
        bool st;
        Node() : len{ 0 }, link{ 0 }, next{} , st(1) {}
    };

    vector<Node> t;

    ACAM() {
        init();
    }

    void init() {
        //设置了一个0号节点长度是-1,避免build时特判
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }

    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }

    int add(const std::string& a) {
        int p = 1;
        for (auto c : a) {
            int x = c - '0';
            if (!t[p].next[x]) {
                int res = newNode();
                t[p].next[x] = res;
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];
        }
        t[p].st = 0;
        return p;
    }

    void build() {
        queue<int> q;
        q.push(1);

        while (!q.empty()) {
            int x = q.front();
            q.pop();

            for (int i = 0; i < M; 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];
                    q.push(t[x].next[i]);
                }
            }
        }

    }

    int next(int p, int x) {
        return t[p].next[x];
    }

    int link(int p) {
        return t[p].link;
    }

    int len(int p) {
        return t[p].len;
    }

    int size() {
        return t.size();
    }


} ac;

void dfs(int n, int sum, string s)
{
    if (sum >= x) {
        if (sum == x) {
            bool ok = 1;
            for (int j = 0; j < n; j++)
            {
                for (int i = j; i < n ; i++)
                {
                    int res = 0;
                    for (int k = j; k <= i; k++)res += s[k] - '0';
                    if (x % res == 0 && res < x)ok = 0;
                }
            }
            if (ok)ac.add(s);///cout << s << endl;
        }
        return;
    }
    for (int i = 1; i < 10; i++) {
        dfs(n + 1, sum + i, s + char(i + '0'));
    }

}

void solve()
{
    cin >> s + 1 >> x;
    int n = strlen(s + 1);
    dfs(0, 0, "");
    ac.build();
    int m = ac.size();
    for (int j = 1; j < m; j++)if (!ac.t[j].st)dp[n][j] = n;

    int ne[10] = {0};
    ne[s[n] - '0'] = n;
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = n;
            if (ac.t[j].st) {
                dp[i][j] = n - i;
                for (int k = 1; k < 10; k++) {
                    if (ne[k])dp[i][j] = min(dp[ne[k]][ac.next(j, k)] + ne[k] - i - 1, dp[i][j]);
                }
            }
        }
        ne[s[i] - '0'] = i;
    }
    //cout<<m<<endl;
    cout << dp[0][1] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}

CF1327G

很明显的多模式串匹配，对所有的 \(t_i\) 建出 AC 自动机，题干保证了 AC 自动机的结点个数 \(cnt \leq 1000\) 。先将每个串的权值挂在终点上，然后在 BFS 的过程中 将结点权值沿 fail 树下传，表示走到 AC 自动机的该点可以获得的权值。

题目要求每个问号填不同的字符，所以我们压缩已选择的状态为 \(mask\) ，那么一个自然的定义就是 \(dp[mask][x]\) 表示已经填入的字符集合为 \(mask\) 同时走到 AC 自动机上 \(x\) 号结点已获得的最大权值。

注意我们可以根据 \(mask\) 中 1 的个数确定已经填了几个问号。

对于相邻的两个问号之间的字符，我们不能存入 \(dp\) 状态表示，但我们可以对中间过程构建 \(ne[x]\) 和 \(val[x]\) 表示 \(x\) 号结点走完这段中间过程可以走到 \(ne[x]\) 号结点，同时获得的权值为 \(val[x]\) 。 每次直接暴力更新即可，复杂度是 \(O(cnt*n)\) 。

转移直接枚举下一个问号要填的字符，时间复杂度为 \(O(14*2^{14}*cnt)\) ，注意不要忘记最后一个问号后面那些字符。

代码 
  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<bits/stdc++.h>
#define ll long long

using namespace std;

struct ACAM {
    static constexpr int M = 14;
    struct Node {
        int len;
        int link;
        ll val;
        array<int, M> next;
        Node() : len{ 0 }, link{ 0 }, next{}, val(0) {}
    };

    vector<Node> t;

    ACAM() {
        init();
    }

    void init() {
        //设置了一个0号节点长度是-1,避免build时特判
        //初始结点因为1号结点。
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }

    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }

    int add(const std::string& a, int v) {
        int p = 1;
        for (auto c : a) {
            int x = c - 'a';
            if (!t[p].next[x]) {
                t[p].next[x] = newNode();
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];
        }
        t[p].val += v;
        return p;
    }

    void build() {
        queue<int> q;
        q.push(1);

        while (!q.empty()) {
            int x = q.front();
            q.pop();

            for (int i = 0; i < M; 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];
                    q.push(t[x].next[i]);
                    t[next(x, i)].val += val(link(next(x, i)));
                }

            }
        }
    }


    int next(int p, int x) {
        return t[p].next[x];
    }

    int link(int p) {
        return t[p].link;
    }

    int len(int p) {
        return t[p].len;
    }

    int size() {
        return t.size();
    }

    int val(int p) {
        return t[p].val;
    }
} ac;

void solve()
{
    int k; cin >> k;
    while (k--) {
        string t; cin >> t;
        int c; cin >> c;

        ac.add(t, c);
    }
    ac.build();

    int n = ac.size();
    string s; cin >> s;

    vector<int>ch(n), e[15];
    vector<ll>val(n);

    vector<vector<ll>>dp(1 << 14, vector<ll>(n, -1e18));
    dp[0][1] = 0;

    int cnt = 0;

    for (int j = 0; j < (1 << 14); j++) {
        int res = 0;
        for (int i = 0; i < 14; i++)res += (j >> i & 1);
        e[res].push_back(j);
    }

    for (int i = 1; i < n; i++)ch[i] = i;
    for (auto c : s) {
        if (c == '?')
        {
            for (auto j : e[cnt])
            {
                for (int i = 0; i < 14; i++)
                {
                    if (j >> i & 1)continue;
                    for (int k = 1; k < n; k++) {
                        int ne = ac.next(ch[k], i);
                        dp[j ^ (1 << i)][ne] = max(dp[j ^ (1 << i)][ne], dp[j][k] + val[k] + ac.val(ne));
                    }
                }
            }
            cnt++;
            for (int i = 1; i < n; i++)ch[i] = i, val[i] = 0;
        }
        else {
            for (int i = 1; i < n; i++)ch[i] = ac.next(ch[i], c - 'a'), val[i] += ac.val(ch[i]);
        }
    }
    ll res = -1e18;
    for (auto j : e[cnt])
        for (int k = 1; k < n; k++)res = max(res, dp[j][k] + val[k]);
    cout << res << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}