C - Lexicographically Maximum Subsequence
You've got string s, consisting of only lowercase English letters. Find its lexicographically maximum subsequence.
We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk(1 ≤ p1 < p2 < ... < pk ≤ |s|) a subsequence of string s = s1s2... s|s|.
String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ... , x|y| = y|y|, or exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 1. Characters in lines are compared like their ASCII codes.
Input
The single line contains a non-empty string s, consisting only of lowercase English letters. The string's length doesn't exceed 105.
Output
Print the lexicographically maximum subsequence of string s.
Example
ababba
bbba
abbcbccacbbcbaaba
cccccbba
Note
Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).
The first sample: aBaBBA
The second sample: abbCbCCaCbbCBaaBA
这个题目就是要求出子串中字典序最大的.
由于本题有许多方法,那我就讲一讲我自己的好了.
由于我们要尽量挑字典序最大的字符作为开头(首关键字并不是长度!),所以,我们要记录当前字符串的最大字符,然后,如果剩下的字符里面,已经不存在这个最大的字符,那么这个字符就下调,知道存在.
这样一个纯模拟的过程就好了,不过不知道为什么我在比赛中时间用的稍微有点多......
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
],nxt[],R[];
],c;
int read(){
,f=; char ch=getchar();
'){if (ch=='-') f=-f; ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
int main(){
scanf("%s",a),len=strlen(a),c='a';
memset(las,,sizeof las);
memset(nxt,,sizeof nxt);
; i>=; i--) ) las[a[i]-'a']=i,nxt[i]=i,R[a[i]-'a']=i;
else nxt[i]=las[a[i]-'a'],las[a[i]-'a']=i;
; i<len; i++) if (c<a[i]) c=a[i];
; i<len; i++) if (a[i]==c){
putchar(c); if (nxt[i]!=i) continue;
);
}
;
}