最長不重復子串的高效實現

翻出了N年前找工時練習寫的代碼，覺得這個還可以，查找英文字符串中第一個出現的最長不重復子串。 只需要一次遍歷即可，不過只適用於英文。

char* GetMaxSubStr( char*str )
{
    int hash[256]; //hash記錄每個字符的出現位置
    int i = 0;
    for ( ;i< 256;i++)//初始化
    {
        hash[i] = -1;
    } www.2cto.com
    int CurrentStart=0,CurrentLength = 0,MaxStart=0,MaxEnd=0;
    int strLen = strlen( str );
    for(i=0;i<strLen;i++)
    {
        if(CurrentStart>hash[str[i]]) //如果沒有重復
        {
            hash[str[i]]=i;
        }
        else
        {
            CurrentLength=i-CurrentStart; //當前長度
            if(CurrentLength>MaxEnd-MaxStart)//如果當前長度最長
            {
                MaxEnd=i;
                MaxStart=CurrentStart;
            }
            CurrentStart=hash[str[i]]+1; //更新當前最長的起點
            hash[str[i]]=i; //更新字符出現的位置
        }
    }
    if ( MaxEnd == 0 )//沒有重復字符，返回源串
    {
        char*reStr = new char[ strLen+1 ];
        strcpy( reStr,str );
        return reStr;
    }
    int MaxLength=MaxEnd-MaxStart;
    char*reStr = new char[ MaxLength +1 ];
    memset( reStr,0,MaxLength+1);
    strncpy( reStr,str+MaxStart,MaxLength );
    return reStr;
}

摘自：ifeng專欄