Input
输入包含多个测试用例,每组测试用例输入一行由小写英文字符a,b,c…x,y,z组成的字符串,字符串的长度不大于10000。
Output
对于每组测试用例,输出最大长度的不重复子串长度。
Sample Input
absd
abba
abdffd
abba
abdffd
Sample Output
4
2
4
2
4
Hint
动态规划
Source
阿尔卡特2013年实习生招聘笔试题
Code
方法一
#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; }
方法二
/**注意,以“asdfsd”为例,当检测到第二个s时,指针应回到第一个s处重新检测*/ #include <iostream> #include<stdio.h> #include <string.h> int a[30]; char str[10010]; int MAX(int a,int b) { return a>b?a:b; } int main() { while(scanf("%s",str)!=EOF) { memset(a,0,sizeof(a)); int max=0,count=0; for(int i=0;i< strlen(str);i++) { if(a[str[i]-'a']>0) { i = a[str[i]-'a']-1;//减去自加的1 memset(a,0,sizeof(a)); max = MAX(max,count); count = 0; } else { a[str[i]-'a'] = i+1;//加一目的为防止第一个字节存储为0 在if判断时忽略 count++; } } max = MAX(max,count); printf("%d\n",max); } }