算法字符串系列的第四篇文章，计算给定字符串的最长无重复子串。
这篇文章主要介绍两种方法，一种是基于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;
}
}
}
结果：
2.动态规划+hash
首先理解，动态规划算法的思想，将问题分解为子问题的解，找到重叠子问题和最优子结构，对需要重复计算的结果进行存储。在这里最优子结构很好理解，在所有无重复子串中，长度最长的就是最优的。而重叠子问题呢？简单的理解，就是当前的LNRS串可以由上一次计算的LNRS得到。
重叠子问题：我们考虑两种情况。
- 当前的字符和前面的字符没有重复，那么到当前字符的最长无重复子串就应该在上次求得的LNRS串长度+1，；
- 如果当前的字符有冲突，那么有两种情况需要分析。第一，如果和它冲突的字符在当前最长无重复子串的起始位置前面，那么很明显，对计算当前的LNRS串没有影响，还是在上次基础上+1；如果冲突字符在当前的LNRS串开始位置之后，那么就从后一个位置计算无重复子串的长度。
而hash在这里就是帮助我们判断是否重复，而不用回溯子串。
代码
理解了上面提到的重叠子问题之后，下面的问题就简单多了。
代码中需要注意的地方：
- dp[]记录第i位的无重复子串，这个子串不一定是全局最长子串，但是针对第i个字符是最长的。所以需要比较所有的dp[i]，来确定最长的。
- 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;
}
}
}
结果：
3.dp+hash优化的问题
我们看dp[i] = dp[i-1]+1;可以理解为就是在更新当前i位的最优解，在看代码中更新dp[i]的部分，再使用到dp[i-1]的地方都只是在上一次的基础上+1，看到这里我们就很容易做出优化策略了。可以不用n位长的数组dp[i]来存储当前的最优解，而只用一个变量来记录就可以了，优化方案很简单，就不贴代码了。
优化：用一个变量来代替dp[]。
总结：
最长回文子串的问题：关注子串中的对称关系。
最长无重复子串为题：关注子串中字符的唯一性，善用hash。
动态规划法，对需要重复计算的问题，可以选保存下来，减少计算的时间复杂度。
