Language: C++

---
layout: post
title:  "AtCoder Regular Contest 081 E"
date:   2017-08-20
excerpt: "interesting problem."
tag:
- string
- algorithm
- ACM
- interesting problem
comments: true
feature: /assets/img/stock/images-stock-photo-Yb054.jpg
---

## Problem Information

source: [It's from the Regular Contest 081 of the AtCoder](http://arc081.contest.atcoder.jp/tasks/arc081_c)

## Description

给出一个字符串 \\(A\\) ，求出一个不属于它的子串的最短字符串，若有多个则取字典序最小的。<br>

数据范围：<br>
* \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
* \\(A\\) consists of lowercase English letters.<br>


## Input

\\(A\\) <br>


## Output

Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of \\(A\\). <br>

## Sample Input
 
~~~
atcoderregularcontest
abcdefghijklmnopqrstuvwxyz
frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn
~~~

## Sample Output
~~~
b
aa
aca
~~~

## Solution

首先，字典序最小可以通过从小到大确定答案来解决。那么，我们只需要知道怎么找到最短的非子串字符串。 <br>

我们考虑任意一个非子串的字符串，它一定是匹配到了原串的某一个位置，且在该位置后的字符少于 \\(26\\) 种，
那么我们添加一个没有出现过的字符即可凑出一个非子串的字符串。那么最短的

## AC code

```c++
char str[MaxN];
int loc[MaxN][26], to[26], dep[MaxN];
void solve()
{
	int len = strlen(str);
	for(int i=0;i<26;i++) to[i] = len+1;
	for(int i=len;i>=0;i--)
	{
		memcpy(loc[i], to, sizeof(to));
		to[str[i-1]-'a'] = i;
	}
	for(int i=len;i>=0;i--)
	{
		dep[i] = len+1;
		for(int j=0;j<26;j++)
		{
			dep[i] = min(dep[i], dep[loc[i][j]]+1);
		}
	}
	int u = 0,v;
	while(u!=len+1)
	{
		for(v=0;v<26;v++)
		{
			if(cost[u]==dep[loc[u][v]]+1) break;
		}
		printf("%c", v+'a');
		u = loc[u][v];
	}
	puts("");
}
int main()
{
	while(~scanf("%s", &str))
		solve();
}
```

Compiler output:
a.cc:4:14: error: invalid digit "8" in octal constant
    4 | date:   2017-08-20
      |              ^~
a.cc:15:1: error: stray '##' in program
   15 | ## Problem Information
      | ^~
a.cc:17:12: warning: missing terminating ' character
   17 | source: [It's from the Regular Contest 081 of the AtCoder](http://arc081.contest.atcoder.jp/tasks/arc081_c)
      |            ^
a.cc:17:12: error: missing terminating ' character
   17 | source: [It's from the Regular Contest 081 of the AtCoder](http://arc081.contest.atcoder.jp/tasks/arc081_c)
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:19:1: error: stray '##' in program
   19 | ## Description
      | ^~
a.cc:21:16: error: stray '\' in program
   21 | 给出一个字符串 \\(A\\) ，求出一个不属于它的子串的最短字符串，若有多个则取字典序最小的。<br>
      |                ^
a.cc:21:17: error: stray '\' in program
   21 | 给出一个字符串 \\(A\\) ，求出一个不属于它的子串的最短字符串，若有多个则取字典序最小的。<br>
      |                 ^
a.cc:21:20: error: stray '\' in program
   21 | 给出一个字符串 \\(A\\) ，求出一个不属于它的子串的最短字符串，若有多个则取字典序最小的。<br>
      |                    ^
a.cc:21:21: error: stray '\' in program
   21 | 给出一个字符串 \\(A\\) ，求出一个不属于它的子串的最短字符串，若有多个则取字典序最小的。<br>
      |                     ^
a.cc:21:24: error: extended character 。 is not valid in an identifier
   21 | 给出一个字符串 \\(A\\) ，求出一个不属于它的子串的最短字符串，若有多个则取字典序最小的。<br>
      |                        ^
a.cc:24:3: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |   ^
a.cc:24:4: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |    ^
a.cc:24:9: error: extended character ≤ is not valid in an identifier
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |         ^
a.cc:24:11: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |           ^
a.cc:24:12: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |            ^
a.cc:24:15: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |               ^
a.cc:24:16: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |                ^
a.cc:24:19: error: extended character ≤ is not valid in an identifier
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |                   ^
a.cc:24:23: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |                       ^
a.cc:24:24: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |                        ^
a.cc:24:36: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |                                    ^
a.cc:24:37: error: stray '\' in program
   24 | * \\( 1 ≤ \\|A\\| ≤ 2 \\times 10^5 \\) <br>
      |                                     ^
a.cc:25:3: error: stray '\' in program
   25 | * \\(A\\) consists of lowercase English letters.<br>
      |   ^
a.cc:25:4: error: stray '\' in program
   25 | * \\(A\\) consists of lowercase English letters.<br>
      |    ^
a.cc:25:7: error: stray '\' in program
   25 | * \\(A\\) consists of lowercase English letters.<br>
      |       ^
a.cc:25:8: error: stray '\' in program
   25 | * \\(A\\) consists of lowercase English letters.<br>
      |        ^
a.cc:28:1: error: stray '##' in program
   28 | ## Input
      | ^~
a.cc:30:1: error: stray '\' in program
   30 | \\(A\\) <br>
      | ^
a.cc:30:2: error: stray '\' in program
   30 | \\(A\\) <br>
      |  ^
a.cc:30:5: error: stray '\' in program
   30 | \\(A\\) <br>
      |     ^
a.cc:30:6: error: stray '\' in program
   30 | \\(A\\) <br>
      |      ^
a.cc:33:1: error: stray '##' in program
   33 | ## Output
      | ^~
a.cc:35:141: error: stray '\' in program
   35 | Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of \\(A\\). <br>
      |                                                                                                                                             ^
a.cc:35:142: error: stray '\' in program
   35 | Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of \\(A\\). <br>
      |                                                                                                                                              ^
a.cc:35:145: error: stray '\' in program
   35 | Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of \\(A\\). <br>
      |                                                                                                                                                 ^
a.cc:35:146: error: stray '\' in program
   35 | Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of \\(A\\). <br>
      |                                                                                                                                                  ^
a.cc:37:1: error: stray '##' in program
   37 | ## Sample Input
      | ^~
a.cc:45:1: error: stray '##' in program
   45 | ## Sample Output
      | ^~
a.cc:52:1: error: stray '##' in program
   52 | ## Solution
      | ^~
a.cc:54:1: error: extended character 。 is not valid in an identifier
   54 | 首先，字典序最小可以通过从小到大确定答案来解决。那么，我们只需要知道怎么找到最短的非子串字符串。 <br>
      | ^
a.cc:54:1: error: extended character 。 is not valid in an identifier
a.cc:56:90: error: stray '\' in program
   56 | 我们考虑任意一个非子串的字符串，它一定是匹配到了原串的某一个位置，且在该位置后的字符少于 \\(26\\) 种，
      |                                                                                          ^
a.cc:56:91: error: stray '\' in program
   56 | 我们考虑任意一个非子串的字符串，它一定是匹配到了原串的某一个位置，且在该位置后的字符少于 \\(26\\) 种，
      |                                                                                           ^
a.cc:56:95: error: stray '\' in program
   56 | 我们考虑任意一个非子串的字符串，它一定是匹配到了原串的某一个位置，且在该位置后的字符少于 \\(26\\) 种，
      |                                                                                               ^
a.cc:56:96: error: stray '\' in program
   56 | 我们考虑任意一个非子串的字符串，它一定是匹配到了原串的某一个位置，且在该位置后的字符少于 \\(26\\) 种，
      |                                                                                                ^
a.cc:57:1: error: extended character 。 is not valid in an identifier
   57 | 那么我们添加一个没有出现过的字符即可凑出一个非子串的字符串。那么最短的
      | ^
a.cc:59:1: error: stray '##' in program
   59 | ## AC code
      | ^~
a.cc:61:1: error: stray '`' in program
   61 | ```c++
      | ^
a.cc:61:2: error: stray '`' in program
   61 | ```c++
      |  ^
a.cc:61:3: error: stray '`' in program
   61 | ```c++
      |   ^
a.cc:98:1: error: stray '`' in program
   98 | ```
      | ^
a.cc:98:2: error: stray '`' in program
   98 | ```
      |  ^
a.cc:98:3: error: stray '`' in program
   98 | ```
      |   ^
a.cc:1:1: error: expected unqualified-id before '--' token
    1 | ---
      | ^~
a.cc:63:9: error: 'MaxN' was not declared in this scope
   63 | int loc[MaxN][26], to[26], dep[MaxN];
      |         ^~~~
a.cc:63:32: error: 'MaxN' was not declared in this scope
   63 | int loc[MaxN][26], to[26], dep[MaxN];
      |                                ^~~~
a.cc: In function 'void solve()':
a.cc:66:26: error: 'str' was not declared in this scope; did you mean 'std'?
   66 |         int len = strlen(str);
      |                          ^~~
      |                          std
a.cc:66:19: error: 'strlen' was not declared in this scope
   66 |         int len = strlen(str);
      |                   ^~~~~~
a.cc:1:1: note: 'strlen' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
  +++ |+#include <cstring>
    1 | ---
a.cc:70:24: error: 'loc' was not declared in this scope
   70 |                 memcpy(loc[i], to, sizeof(to));
      |                        ^~~
a.cc:70:17: error: 'memcpy' was not declared in this scope
   70 |                 memcpy(loc[i], to, sizeof(to));
      |                 ^~~~~~
a.cc:70:17: note: 'memcpy' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
a.cc:75:17: error: 'dep' was not declared in this scope
   75 |                 dep[i] = len+1;
      |                 ^~~
a.cc:78:50: error: 'loc' was not declared in this scope
   78 |                         dep[i] = min(dep[i], dep[loc[i][j]]+1);
      |                                                  ^~~
a.cc:78:34: error: 'min' was not declared in this scope
   78 |                         dep[i] = min(dep[i], dep[loc[i][j]]+1);
      |                                  ^~~
a.cc:86:28: error: 'cost' was not declared in this scope; did you mean 'const'?
   86 |                         if(cost[u]==dep[loc[u][v]]+1) break;
      |                            ^~~~
      |                            const
a.cc:86:37: error: 'dep' was not declared in this scope
   86 |                         if(cost[u]==dep[loc[u][v]]+1) break;
      |                                     ^~~
a.cc:86:41: error: 'loc' was not declared in this scope
   86 |