算法-字符串之最长无重复子串

算法字符串系列的第四篇文章，计算给定字符串的最长无重复子串。

---

这篇文章主要介绍两种方法，一种是基于hash的思想，一种是基于dp（动态规划）+hash来实现，这两种方法都不难，容易理解。下面会详细介绍。

1.hash实现

这类问题应该学会分析结果的特点，比如说前面的最长回文子串，是利用了回文串的对称性，那么无重复子串呢，想到无重复，可以想到可以使用hash，当新的字符来了，有冲突，就说明前面是有重复的。
算法思想：两次循环得到所有的子串，用hash判断是否重复。

代码
代码中需要注意的地方：
1.以字符对应的ASCII码作为hash值，visit[str[i]]=0，说明str[i]这个字符还没有出现过，=1说明有重复。
2.在每次内层循环重新开始的时候，都要将visit初始化为0，每次内层循环求的是str[i...j]之间的最长子串，要判断他们之间是否有重复，所以要确保i...j这个范围内的visit都没初始化为0了，否则出现i...j之间的字符和这个范围之外的字符重复就会导致结果出错。

/*求所有的子串，用hash判断是否是重复的，*/
void LNRS_hash(char *str, int size)
{
    int i, j;
     for (i = 0; i < size; ++i)
    {
        memset(visit, 0, sizeof(visit));//初始化visit为0
        visit[str[i]] = 1;
        for (j = i + 1; j < size; ++j)
        {
            if (visit[str[j]] == 0)
            {
                visit[str[j]] = 1;
            }
            else
            {
                if (j - i > longest)
                {
                    longest = j - i;
                    start = i;
                }
                break;
             }
        }
        if ((j == size) && (j - i > longest))
        {
            longest = j - i;
            start = i;
        }
    }
}

结果：

基于hash求最长无重复子串

2.动态规划+hash

首先理解，动态规划算法的思想，将问题分解为子问题的解，找到重叠子问题和最优子结构，对需要重复计算的结果进行存储。在这里最优子结构很好理解，在所有无重复子串中，长度最长的就是最优的。而重叠子问题呢？简单的理解，就是当前的LNRS串可以由上一次计算的LNRS得到。

重叠子问题：我们考虑两种情况。

1. 当前的字符和前面的字符没有重复，那么到当前字符的最长无重复子串就应该在上次求得的LNRS串长度+1，；
2. 如果当前的字符有冲突，那么有两种情况需要分析。第一，如果和它冲突的字符在当前最长无重复子串的起始位置前面，那么很明显，对计算当前的LNRS串没有影响，还是在上次基础上+1；如果冲突字符在当前的LNRS串开始位置之后，那么就从后一个位置计算无重复子串的长度。

而hash在这里就是帮助我们判断是否重复，而不用回溯子串。

代码
理解了上面提到的重叠子问题之后，下面的问题就简单多了。
代码中需要注意的地方：

1. dp[]记录第i位的无重复子串，这个子串不一定是全局最长子串，但是针对第i个字符是最长的。所以需要比较所有的dp[i]，来确定最长的。
2. visit[i]在这里不止是当做hash来使用了，它不止用来判断是否重复，还记录最近的重复位置。eg：abcdahijka，针对最后一个a，visit[a]记录的应该是第二个a的位置，记录第一个a的位置毫无意义，因为从第一个a后面的b...到最后一个a之间，还有一个a,所以其实b到第二个a之间的字符肯定不会在a3的最长重复子串内。

/* LNRS dp + hash 记录下标 */
void LNRS_dp_hash(char * str, int size)
{
    int *dp = (int*)malloc(sizeof(int)*size);

    memset(visit, -1, sizeof(visit));
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    visit[str[0]] = 0;
    int last_start = 0;

    for (int i = 1; i < size; i++) {
        if (visit[str[i]] == -1){
            dp[i] = dp[i - 1] + 1;
            visit[str[i]] = i;//记录字符的下标
        }
        else {/*和visit[str[i]]位置的字符冲突*/
            if (last_start <= visit[str[i]])
            {
                dp[i] = i - visit[str[i]];
                last_start = visit[str[i]] + 1;
                visit[str[i]] = i;//更新最近的重复位置
          }
            else{
                dp[i] = dp[i - 1] + 1;
                visit[str[i]] = i;//记录字符的下标
            }
        }

        if (dp[i]>longest)
        {
            longest = dp[i];
            start = i - longest + 1;
        }
    }
}

结果：

dp+hash最长无重复子串

3.dp+hash优化的问题

我们看dp[i] = dp[i-1]+1;可以理解为就是在更新当前i位的最优解，在看代码中更新dp[i]的部分，再使用到dp[i-1]的地方都只是在上一次的基础上+1，看到这里我们就很容易做出优化策略了。可以不用n位长的数组dp[i]来存储当前的最优解，而只用一个变量来记录就可以了，优化方案很简单，就不贴代码了。
优化：用一个变量来代替dp[]。

总结：

最长回文子串的问题：关注子串中的对称关系。
最长无重复子串为题：关注子串中字符的唯一性，善用hash。
动态规划法，对需要重复计算的问题，可以选保存下来，减少计算的时间复杂度。