最长不重复子串

用visit数组记录出现过的地方

dp的时候注意一个问题就可以：

abcdacbd来看看如果遇到重复的该怎么处理：

遇到第二个a前都没有问题，第二次遇到a，然后肯定是更新a的位置的dp[4] = 4-0 = 4,  

                                   第二次遇到c,                 更新c的位置为dp[5] = 5-2 = 3;

               然后问题来了，第二次遇到b，从第一个b和第二个b之间已经重复c了，所以只能更新dp[6] = dp[5]+1，所以这里的问题在于，如何标记dp[i]=dp[i-1]+1还是dp[i]=i-visit[a[i]]..............所以这里判断的方法就是，使用一个指针last标记刚刚更新过的地方，比如更新c后，标记last = 2(就是第一个c),然后

if(visit[a[i]] < last)//说明第一个b和第二个b直接有c重复了
    dp[i] = dp[i-1]+1;
else
    dp[i] = i - visit[a[i]];
    last = visit[a[i]];

/* 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;
                visit[arr[i]] = i; /* 更新最近重复位置 */
            }
        }
        if(curlen > maxlen)
        {
            maxlen = curlen;
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}