ARC-081-E

发表于 |

题目

给一个长度为$N$的字符串$S$，求不是$S$的子序列的最短的字符串，有多个的话，输出字典序最小的。

数据范围

$1\leq N \leq 2\times 10^5$

做法

先考虑求最短的“不是S串的子序列”的串的长度，再求其字典序最小的串。

考虑不是S的子序列的串T所具有的性质。

  1. 如果$T_0$不在S中出现，那么T只要包括$T_0$一个字符就行了。
  2. 如果$T_0$在S中出现，设$T_0$在S中最先出现的位置为i，那么T不是S的子序列当且仅当$SuffT_1$不是$SuffS_i$的子序列。

考虑DP。
$dp[i]:=$不是$SuffS_i$的子序列的最短长度。
转移的过程就是对每个S的后缀，枚举以$a,b,c,\cdots,z$开头的不是此后缀的字串的最短的字符串。
$dp[i]=min_c{dp[next(i,c)]} + 1$

其中，$next(i,c):=$i后面最近的c出现的位置。

字典序最小可以通过记录每次DP的决策来记录。比如，第一个字母就是在求整个子串的最短的答案时的DP决策。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
int N;
char s[MAX_N];
int nxt[MAX_N][26], pos[26];
int dp[MAX_N];
int a[MAX_N];
int main()
{
  scanf("%s", s);
  N = strlen(s);
  for (int i = 0; i < 26; ++i) pos[i] = N;
  for (int i = N - 1; i >= 0; --i) {
    for (int j = 0; j < 26; ++j) {
      nxt[i][j] = pos[j];
    }
    pos[s[i] - 'a'] = i;
  }
  dp[N] = 0;
  memset(a, -1, sizeof a);
  for (int i = N - 1; i >= 0; --i) {
    int mi = INT_MAX;
    for (int j = 0; j < 26; ++j) {
      int to = nxt[i][j];
      if (mi > dp[to]) {
        mi = dp[to];
        a[i] = j;
      }
    }
    dp[i] = mi + 1;
  }
  int cur;
  int mi = INT_MAX;
  for (int i = 0; i < 26; ++i) {
    int to = pos[i];
    if (mi > dp[to]) {
      mi = dp[to];
      cur = i;
    }
  }
  int cnt = 0, p;
  while (cur != -1) {
    printf("%c", cur + 'a');
    if (cnt == 0) {
      p = pos[cur];
      cur = a[p];
    } else {
      p = nxt[p][cur];
      cur = a[p];
    }
    ++cnt;
  }
  printf("\n");
  return 0;
}