“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛----D-CSL的字符串

首先发出题目链接：
链接：https://ac.nowcoder.com/acm/contest/551/D
来源：牛客网

题目如下：


所输出的字符串应该是属于原字符串的字序典最小的子串，并且每个字符有且只能重复一次。

我们可以看做从字符串的首位出发，一个个选取符合条件的字符并排序，形成一个满足条件的子串。

我们可以从原字符串的末尾从头往前遍历，直到遍历到新的满足条件的子串的最后一个字符所选取它的的位置的下一个位置为止（子串最后那个字符你从原字符串哪里选取了它，你就从前往后遍历到它的位置的下一个位置为止），每次遍历更新所选择的字符，直到遍历结束，最后选择的字符即为子字符串下一个位置的字符。

对于每次选取的字符（更新选择）应该符合以下条件：

（1）这个字符没选择过，即在新的满足条件的子串中没有出现过（子串每个字符只能出现一次）；

（2）这个字符在在原字符串的后面再未出现过（比如字符串zaac，‘z’这个字符在它出现位置之后再没有出现过）；

或者

（3）这个字符比当前已选择字符的ASCII码要小或者等于。

其中，条件（1）是首要条件，条件（2）（3）是次要条件（其中一个成立，就可以更新选择）。

对于每次更新选择，我们可以将每次选择的字符进行标记，避免后来的更新选择到了与之前选择相同的字符。

ps：所有可能出现字符ACSII（0x21~0x7E）,共94个字符。

举个例子：

比如说字符串cbacbacba

首先遍历一遍字符串，得到次字符串的字符种类cnt。

（此情况下cnt=3）

下面开始进行cnt次循环遍历

（粗体代表目前选择的字符，删除线 代表被标记过的字符）

由于子字符串为空，所以我们第一次遍历原字符串应该是从末尾到首位。

1.第一次遍历：

c b a c b a c b a
（1）选择字符‘a’并标记（字符‘a’未在子串中出现过，也没有选择过（标记过，或者说在字符串此位置之后没有出现过））。

c b a c b a c b a
（2）字符‘b’满足条件，将选择更新为字符‘b’并标记（字符‘b’未在子串中出现过，也没有选择过）。

c b a c b a c b a
（3）字符‘c’满足条件，将选择更新为字符‘c’并标记（字符‘c’未在子串中出现过，也没有选择过）。

c b a c b a c b a
（4）字符‘a’满足条件，将选择更新为字符‘a’并标记（字符‘a’未在子串中出现过，但是比当前选择的字符‘c’要小）。

c b a c b a c b a
（5）字符‘b’不满足条件，不进行更新，进行标记（字符‘b’未在子串中出现过，但是被选择过（标记过，在字符串此位置之后出现过））。

c b a c b a c b a
（6）字符‘c’不满足条件，不进行更新，进行标记（字符‘c’未在子串中出现过，但是被选择过）。

c b a c b a c b a
（7）字符‘a’满足条件，将选择更新为字符‘c’并标记（字符串未在子串中出现过，但是和当前选择的字符‘a’相等）

c b a c b a c b a
（8）字符‘b’不满足条件，不进行更新，进行标记（字符‘b’未在子串中出现过，但是被选择过）

c b a c b a c b a
（9）字符‘c’不满足条件，不进行更新，进行标记（字符‘c’未在子串中出现过，但是被选择过）

第一次遍历完毕，选择字符‘a’为子串的第一个字符，故字符‘a’之前的字符在不能被选入子串，所以下次遍历到字符‘a’下一个位置的字符‘c’为止，并且将所有字符标记全部删除。

2.第二次遍历

c b a c b a c b a
（1）字符‘a’不满足条件，不进行更新，进行标记（字符‘a’在子串中出现过）。

c b a c b a c b a
（2）选择并标记字符‘b’（字符‘b’未在子串中出现过，也没有选择过）。

c b a c b a c b a
（3）字符‘c’满足条件，将选择更新为字符‘c’并标记（字符‘c’未在子串中出现过，也没有选择过）。

c b a c b a c b a
（4）字符‘a’不满足条件，不进行更新，进行标记（字符‘a’在子串中出现过）。

c b a c b a c b a
（5）字符‘b’满足条件，将选择更新为字符‘b’并标记（字符‘b’未在子串中出现过，但是比当前选择的字符‘c’要小）。

c b a c b a c b a
（6）字符‘c’不满足条件，不进行更新，进行标记（字符‘c’未在子串中出现过，但是被选择过）。

第二次遍历完毕，选择字符‘b’为子串的第二个字符，故字符‘b’之前的字符在不能被选入子串，所以下次遍历到字符‘b’下一个位置的字符‘a’为止，并且将所有字符标记全部删除。

3.第三次遍历

c b a c b a c b a
（1）字符‘a’不满足条件，不进行更新，进行标记（字符‘a’在子串中出现过）。

c b a c b a c b a
（2）字符‘b’不满足条件，不进行更新，进行标记（字符‘b’在子串中出现过）。

c b a c b a c b a
（3）字符‘c’满足条件，将选择更新为字符‘c’并标记（字符‘c’未在子串中出现过，也没有选择过）。

c b a c b a c b a
（4）字符‘a’不满足条件，不进行更新，进行标记（字符‘a’在子串中出现过）。

第三次遍历完毕，选择字符‘c’为子串的第三个字符，cnt次循环结束，此时子串拥有所有的cnt的字符，且字序典最小，子串为“abc”。

下面放出代码：

#include <string>
#include <iostream>
#include <string.h>
using namespace std;
string s;//原字符串s
bool check[95]={false},exist[95]={false};
//check数组用来表示字符是否被标记，exist数组用来表示选择的字符是否在子串里出现过。
int len,pos=0,head,dpos,cnt=0;
//len是原字符串的长度，pos是子字符串最后一个字符在原字符串的位置，dpos是pos的下一个位置，用来表示从尾往前遍历的终点。
//head表示当前选择的字符，cnt是原字符串字符的种类。
int main(){cin>>s;len=s.size();int i;for(int i=0;i<len;i++){//计算原字符串字符种类if(!check[s[i]-0x21])cnt++;check[s[i]-0x21]=true;}for(i=1;i<=cnt;i++){//有多少种字符，就遍历多少次memset(check,false,sizeof(check));//每次遍历开始要清楚所有标记head=0x7E;//初始化选择的字符串，更好的实现第（3）个条件int j;for(j=len-1;j>=pos;j--){//从尾到pos进行遍历原字符串if(!exist[s[j]-0x21] && (s[j]<=head || !check[s[j]-0x21])){//if（字符在子字符串未出现过 && （这个字符比当前选择的字符小 || 这个字符没有被选择过（标记过）））check[s[j]-0x21]=true;//标记字符head=s[j];//更新选择的字符dpos=j;//更新选择的字符在原字符串的位置}}pos=dpos+1;//更新下一次遍历的终点exist[head-0x21]=true;//表示这个字符成为子字符串下一个位置的字符printf("%c",head);//输出这个字符}
}