首页 > ACM题库 > 九度OJ > 九度-1530-最长不重复子串[解题代码]
2013
12-13

九度-1530-最长不重复子串[解题代码]

题目来源:阿尔卡特2013年实习生招聘笔试题

题目描述:

最长不重复子串就是从一个字符串中找到一个连续子串,该子串中任何两个字符都不能相同,且该子串的长度是最大的。

输入:

输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c…x,y,z组成的字符串,字符串的长度不大于10000。

输出:

对于每组测试用例,输出最大长度的不重复子串长度。

样例输入:
absd
abba
abdffd
样例输出:
4
2
4

cpp 代码如下:
#include <stdio.h>
#include <string.h>
char str[10002];
int has[26],cnt,ans,i,j,s;
int main(){
	while(~scanf("%s",str)){
		ans=0,cnt=0,s=1;
		memset(has,0,sizeof(has));
		for( i=0; str[i]; i++){
			if(has[str[i]-'a'] < s) cnt++;
			else{
				cnt=i-has[str[i]-'a'] + 1;
				s=has[str[i]-'a'];
			}
			has[str[i]-'a'] = i+1;
			if(cnt > ans) ans = cnt;
		}
		printf("%d\n",ans);
	}
	return 0;
}

/**************************************************************
	Problem: 1530
	User: coder
	Language: C
	Result: Accepted
	Time:20 ms
	Memory:924 kb
****************************************************************/