對(duì)于一個(gè)字符串,請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法，找到字符串的最長(zhǎng)無(wú)重復(fù)字符的子串長(zhǎng)度。
窮舉肯定是不行的，這個(gè)問(wèn)題要用到類似于動(dòng)態(tài)規(guī)劃的算法：
已知字符串A，設(shè)定數(shù)組len，另len[i]表示以元素A[i]結(jié)尾的，最長(zhǎng)的無(wú)重復(fù)子串。只要求出來(lái)len數(shù)組中的最大值，即為問(wèn)題的解。
目前的問(wèn)題是，已知len[i-1],如何求len[i]?

我們當(dāng)前處理A[i],已知len[i-1]==5,就可以知道以A[i-1]做結(jié)尾的最大無(wú)重復(fù)子串的長(zhǎng)度是5，就可以找到該子串的起始位置p.

1. 因?yàn)锳[i]=='C',如果發(fā)現(xiàn)從A[p..i-1]內(nèi)沒(méi)有出現(xiàn)‘C’,就可以把新成員C納入到該子串中。所以以A[i]為結(jié)尾的最大無(wú)重復(fù)子串是A[p..i].

2. 如果發(fā)現(xiàn)從A[p..i-1]內(nèi)出現(xiàn)‘C’,那么以A[i]為結(jié)尾的最大無(wú)重復(fù)子串，只能是A[q+1..i].

   
   

為了提高搜索某字符在字符串中上一次出現(xiàn)的位置，我們使用一個(gè)哈希表來(lái)存儲(chǔ)。該表初始化所有元素為-1，提高通用性。

    int longestSubstring(string A, int n) {
        //哈希表：每個(gè)元素上次出現(xiàn)的位置
        int pos[256];
        for(int i=0;i<256;++i)
            pos[i]=-1;//初始-1可以統(tǒng)一化使用
        //以i為結(jié)尾的最大無(wú)重復(fù)串長(zhǎng)度
        int *len=new int[n]();
        //初始化0號(hào)字符的情況
        len[0]=1;
        pos[A[0]]=0;
        for(int i=1;i<n;++i){
            //為了處理方便，q的定義與圖示
            int q=pos[A[i]]+1;
            int p=i-len[i-1];
            len[i]=q<p?i-p+1:i-q+1;
            pos[A[i]]=i;
        }
        //找出len數(shù)組中最大值
        int max=0;
        for(int i=0;i<n;++i){
            if(len[i]>max)
                max=len[i];
        }
        delete[] len;
        return max;
    }