算法字符串系列的第四篇文章，計算給定字符串的最長無重復(fù)子串幔妨。
這篇文章主要介紹兩種方法鹦赎，一種是基于hash的思想，一種是基于dp（動態(tài)規(guī)劃）+hash來實現(xiàn)误堡，這兩種方法都不難古话，容易理解。下面會詳細介紹锁施。
1.hash實現(xiàn)
這類問題應(yīng)該學(xué)會分析結(jié)果的特點陪踩，比如說前面的最長回文子串，是利用了回文串的對稱性悉抵，那么無重復(fù)子串呢肩狂，想到無重復(fù)，可以想到可以使用hash基跑，當(dāng)新的字符來了婚温，有沖突描焰，就說明前面是有重復(fù)的媳否。
算法思想：兩次循環(huán)得到所有的子串，用hash判斷是否重復(fù)荆秦。
代碼
代碼中需要注意的地方：
1.以字符對應(yīng)的ASCII碼作為hash值篱竭，visit[str[i]]=0，說明str[i]這個字符還沒有出現(xiàn)過步绸，=1說明有重復(fù)掺逼。
2.在每次內(nèi)層循環(huán)重新開始的時候，都要將visit初始化為0瓤介，每次內(nèi)層循環(huán)求的是str[i...j]之間的最長子串吕喘，要判斷他們之間是否有重復(fù)赘那，所以要確保i...j這個范圍內(nèi)的visit都沒初始化為0了，否則出現(xiàn)i...j之間的字符和這個范圍之外的字符重復(fù)就會導(dǎo)致結(jié)果出錯氯质。
/*求所有的子串募舟，用hash判斷是否是重復(fù)的，*/
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;
}
}
}
結(jié)果：
2.動態(tài)規(guī)劃+hash
首先理解闻察，動態(tài)規(guī)劃算法的思想拱礁，將問題分解為子問題的解，找到重疊子問題和最優(yōu)子結(jié)構(gòu)辕漂，對需要重復(fù)計算的結(jié)果進行存儲呢灶。在這里最優(yōu)子結(jié)構(gòu)很好理解，在所有無重復(fù)子串中钉嘹，長度最長的就是最優(yōu)的鸯乃。而重疊子問題呢？簡單的理解隧期，就是當(dāng)前的LNRS串可以由上一次計算的LNRS得到飒责。
重疊子問題：我們考慮兩種情況。
- 當(dāng)前的字符和前面的字符沒有重復(fù)仆潮，那么到當(dāng)前字符的最長無重復(fù)子串就應(yīng)該在上次求得的LNRS串長度+1宏蛉，；
- 如果當(dāng)前的字符有沖突性置，那么有兩種情況需要分析拾并。第一，如果和它沖突的字符在當(dāng)前最長無重復(fù)子串的起始位置前面鹏浅，那么很明顯嗅义，對計算當(dāng)前的LNRS串沒有影響，還是在上次基礎(chǔ)上+1隐砸；如果沖突字符在當(dāng)前的LNRS串開始位置之后之碗，那么就從后一個位置計算無重復(fù)子串的長度。
而hash在這里就是幫助我們判斷是否重復(fù)季希，而不用回溯子串褪那。
代碼
理解了上面提到的重疊子問題之后，下面的問題就簡單多了式塌。
代碼中需要注意的地方：
- dp[]記錄第i位的無重復(fù)子串博敬，這個子串不一定是全局最長子串，但是針對第i個字符是最長的峰尝。所以需要比較所有的dp[i]偏窝，來確定最長的。
- visit[i]在這里不止是當(dāng)做hash來使用了，它不止用來判斷是否重復(fù)祭往，還記錄最近的重復(fù)位置伦意。eg：abcdahijka，針對最后一個a硼补，visit[a]記錄的應(yīng)該是第二個a的位置默赂，記錄第一個a的位置毫無意義，因為從第一個a后面的b...到最后一個a之間括勺，還有一個a,所以其實b到第二個a之間的字符肯定不會在a3的最長重復(fù)子串內(nèi)缆八。
/* LNRS dp + hash 記錄下標(biāo) */
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;//記錄字符的下標(biāo)
}
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;//更新最近的重復(fù)位置
}
else{
dp[i] = dp[i - 1] + 1;
visit[str[i]] = i;//記錄字符的下標(biāo)
}
}
if (dp[i]>longest)
{
longest = dp[i];
start = i - longest + 1;
}
}
}
結(jié)果：
3.dp+hash優(yōu)化的問題
我們看dp[i] = dp[i-1]+1;可以理解為就是在更新當(dāng)前i位的最優(yōu)解，在看代碼中更新dp[i]的部分疾捍，再使用到dp[i-1]的地方都只是在上一次的基礎(chǔ)上+1奈辰，看到這里我們就很容易做出優(yōu)化策略了÷叶梗可以不用n位長的數(shù)組dp[i]來存儲當(dāng)前的最優(yōu)解奖恰，而只用一個變量來記錄就可以了，優(yōu)化方案很簡單宛裕，就不貼代碼了瑟啃。
優(yōu)化：用一個變量來代替dp[]。
總結(jié)：
最長回文子串的問題：關(guān)注子串中的對稱關(guān)系揩尸。
最長無重復(fù)子串為題：關(guān)注子串中字符的唯一性蛹屿，善用hash。
動態(tài)規(guī)劃法岩榆，對需要重復(fù)計算的問題错负，可以選保存下來，減少計算的時間復(fù)雜度勇边。
