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