284
九度题目1530：最长不重复子串
题目1530：最长不重复子串
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：873
解决：284
题目描述：
最长不重复子串就是从一个字符串中找到一个连续子串，该子串中任何两个字符都不能相同，且该子串的长度是最大的。
输入：
输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于10000。
输出：
对于每组测试用例，输出最大长度的不重复子串长度。
样例输入：
absd
abba
abdffd
样例输出：
4
2
4
来源：
阿尔卡特2013年实习生招聘笔试题
AC代码：
#include<stdio.h>
#include<string.h>
char a[11000];
int b[11000];
int flag[28];
int main()
{
int i,j,n,m,sum,max;
while(scanf("%s",a)!=EOF)
{
n=strlen(a);m=0;
for(i=0;i<n;i++)
{
b[m++]=a[i]-'a';
}
sum=0;max=-9999999;
for(i=0;i<m;i++)//没有回溯就WA了
{
memset(flag,0,sizeof(flag));
sum=0;
for(j=i;j<m;j++)
{
if(!flag[b[j]])
{
flag[b[j]]=1;
sum++;
if(sum>max)
max=sum;
}
else break;
}
}
printf("%d\n",max);
memset(a,0,sizeof(a));
}
return 0;
}
最后更新：2017-04-03 12:56:25