1015 最长不重复子串【阿尔卡特2013年实习生招聘笔试题】

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

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

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

absd
abba
abdffd

4
2
4

动态规划

阿尔卡特2013年实习生招聘笔试题

方法一

#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);
    }
}