upc 6597: Don't Be a Subsequence （字符串的最短不匹配子序列 dp）

6597: Don't Be a Subsequence

时间限制: 1 Sec  内存限制: 128 MB
提交: 237  解决: 45
[提交] [状态] [讨论版] [命题人:admin]

题目描述

A subsequence of a string S is a string that can be obtained by deleting zero or more characters from S without changing the order of the remaining characters. For example, arc, artistic and (an empty string) are all subsequences of artistic; abc and ci are not.
You are given a string A consisting of lowercase English letters. Find the shortest string among the strings consisting of lowercase English letters that are not subsequences of A. If there are more than one such string, find the lexicographically smallest one among them.

Constraints
1≤|A|≤2×105
A consists of lowercase English letters.

输入

Input is given from Standard Input in the following format:
A

输出

Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of A.

样例输入

atcoderregularcontest

样例输出

b

提示

The string atcoderregularcontest contains a as a subsequence, but not b.

【题意】

给出一个字符串，求一个最短的且字典序最小的字符串（以下称为可行串），满足不能与所给串的任意子序列相匹配。

【分析】

设suffx(i)表示以i开头的后缀子串，比如字符串abcde的suffx(3)=cde

设dp[i] 表示suffx(i)串的 可行串 的最小长度

枚举当前后缀串suffx(i) 的第一个字符j，则这个字符一定能和suffx(i)的第一次出现的 j 匹配。

用nxt[j]记录当前后缀串中，第一个出现字符 j 的位置

则：dp[i] = min ( dp[ nxt[j] +1 ] + 1 );

同时记录路径：

 path[i] 表示一个字母，suffx(i) 中以此字母开头，可以得到最短可行串。

to[i] 表示suffx(i)第一个字符放上path[i]之后，可以移动到后面的哪个suffx( i )

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2e5+5;
const int INF=0x3f3f3f3f;
template<class T>bool gmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>bool gmin(T &a,T b){return a>b?a=b,1:0;}
int nxt[MAX];
int dp[MAX];
int path[MAX];
int to[MAX];
char str[MAX];
int main()
{
    while(~scanf("%s",str))
    {
        int len=strlen(str);
        for(int j=0;j<26;j++)nxt[j]=len;
        for(int i=0;i<=len;i++) //多考虑一个后缀串，空串，能匹配所有字符串
            dp[i]=INF;
        dp[len+1]=0;
        //nxt[i]表示字符i在当前后缀串中出现的第一个位置
        for(int i=len-1;i>=0;i--) //遍历每一个后缀串
        {
            nxt[str[i]-'a']=i;
            for(int j=0;j<26;j++)
            {
                if(gmin(dp[i],dp[nxt[j]+1]+1))
                {
                    path[i]=j; //记录下当前后缀第一个字符放哪个字母
                    to[i]=nxt[j]+1; //下一个后缀位置
                }
            }
        }
        int i=0;
        while(i<len)
        {
            printf("%c",path[i]+'a');
            i=to[i];
        }
        putchar('\n');
    }
    return 0;
}