not sub sequence
TimeLimit: 1 Second MemoryLimit: 32 Megabyte
Totalsubmit: 145 Accepted: 48
Description
You have known how to find the longest common subsequence of two sequences.
Today you are not going to solve this problem, but to find the shortest
subsequence that is not in a sequence. For example, given a sequence of
"ABCDEFG", the shortest subsequence not appearing in the sequence is BA, CB, CA
and so on.
Input
The input contains multiple test cases, each a line consisting of a sequence
of capital letters. The length of each sequence is N(2<=N<=999999).
Output
For each test case, output the length of shortest subsequence that not
appearing in the sequence given.
Sample Input
ABCDEFG
DADAADDD
CDBBDCB
Sample Output
2
4
3
ORZ秦牛
诡异的DP。。。。
在I个字符时候需要最好MAX长度的字符串
如果遇到前面没有出现过字母，那么MAX更改为2
如果遇到前面的字母了，只有可能所有前面的字母在MAX长度后都出现了一次，才有可能MAX+1
#include<stdio.h>
#include<string.h>
char s[1200000];
int tot,to;
bool vis[30],que[30];
int main()
{
while(scanf("%s",s)!=EOF)
{
memset(vis,0,sizeof(vis));
memset(que,0,sizeof(que));
char a;
int max=2;;
a=s[0];
tot=1;//标记已经出现的字母种类
to=0;//标记在max这个基础上用所有出现的字母轮换的次数
vis[a-'A']=true;
int l=strlen(s);
for(int i=1;i<l;i++)
{
a=s[i];
if(vis[a-'A'])
{
if(!que[a-'A'])
{
to++;
que[a-'A']=true;
if(to==tot)
{
to=0;
memset(que,0,sizeof(que));
max++;
}
}
}
else
{
vis[a-'A']=true;
tot++;//标记已经出现的字母种类
to=0;//更新为0
memset(que,0,sizeof(que));
max=2;
}
}
printf("%d/n",max);
}
return 0;
}