在英文字符串中找第一个最长不含重复字符的子串高效实现(修改版)
找工时候练习写的代码。翻出来了。
今天有朋友指出来程序运行结果错误,试了下,果然有问题,在下班途中重新整理了思路,修改了代码,整体思路不变,就是加了几行代码,处理字符串的最后部分。求验证结果。
顺便问下,怎么取消文章被评论时收到系统通知的邮件呢?
char*GetSubStr( const char*str )
{
int hash[256]; //hash记录每个字符的出现位置
int i;
for( i = 0;i<256;i++ )
hash[i]=-1;
int CurrentStart=0,MaxStart=0,MaxEnd=0,MaxLength =0,CurrentLength = 0,strLen = strlen(str);
for(i=0;i<strLen;i++)
{
if(CurrentStart>hash[str[i]]) //如果没有重复
{
hash[str[i]]=i;
} www.zzzyk.com
else
{
CurrentLength=i-CurrentStart; //当前长度
if(CurrentLength>MaxEnd-MaxStart)//如果当前长度最长
{
MaxEnd=i;
MaxStart=CurrentStart;
}
CurrentStart=hash[str[i]]+1; //更新当前最长的起点
hash[str[i]]=i; //更新字符出现的位置
}
}
//增加的代码
if( strLen - CurrentStart> CurrentLength)
{
MaxEnd = strLen;
MaxStart=CurrentStart;
}
//
MaxLength=MaxEnd-MaxStart;
char*reStr = new char[MaxLength+1];
reStr[MaxLength]=0;
memcpy( reStr,str+MaxStart,MaxLength );
return reStr;
}
作者:ifeng
补充:软件开发 , C语言 ,