学步园

http://www.ahathinking.com/archives/123.html

题：从一个字符串中找到一个连续子串，该子串中任何两个字符不能相同，求子串的最大长度并输出一条最长不重复子串。

新的子串的长度是与第一个重复的字符的下标有关的，如果该下标在上一个最长子串起始位置之前，则dp[i]
= dp[i-1] + 1，即上一个最长子串的起始位置也是当前最长子串的起始位置；如果该下标在上一个最长子串起始位置之后，则新的子串是从该下标之后开始的。

考虑字符串 bcadac

/* LNRS dp + hash 优化 */
void LNRS_dp_hash_impro(char * arr, int size)
{
    memset(visit, -1, sizeof visit);
    maxlen = maxindex = 0;
    visit[arr[0]] = 0;
    int curlen = 1;
    int last_start = 0;
 
    for(int i = 1; i < size; ++i)
    {
        if(visit[arr[i]] == -1)
        {
            ++curlen;
            visit[arr[i]] = i; /* 记录字符下标 */
        }else
        {
            if(last_start <= visit[arr[i]])
            {
                curlen = i - visit[arr[i]];
                last_start = visit[arr[i]] + 1;
                visit[arr[i]] = i; /* 更新最近重复位置 */
            }else
            {
                ++curlen;
            }
        }
        if(curlen > maxlen)
        {
            maxlen = curlen;
            maxindex = i + 1 - maxlen;
        }
    }
    //应该还是有一个判断
    if (currlen > maxlen)
  .....
    output(arr);
}