i3geek.com
闫庚哲的个人博客

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

进入OJ

Description

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

Input

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

Output

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

Sample Input

absd
abba
abdffd

Sample Output

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

 

赞(0)
未经允许不得转载:爱上极客 » 1015 最长不重复子串【阿尔卡特2013年实习生招聘笔试题】
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址