问题：字符串的最长无重复子串

对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
穷举肯定是不行的，这个问题要用到类似于动态规划的算法：
已知字符串A，设定数组len，另len[i]表示以元素A[i]结尾的，最长的无重复子串。只要求出来len数组中的最大值，即为问题的解。
目前的问题是，已知len[i-1],如何求len[i]?

我们当前处理A[i],已知len[i-1]==5,就可以知道以A[i-1]做结尾的最大无重复子串的长度是5，就可以找到该子串的起始位置p.

1. 因为A[i]=='C',如果发现从A[p..i-1]内没有出现‘C’,就可以把新成员C纳入到该子串中。所以以A[i]为结尾的最大无重复子串是A[p..i].

2. 如果发现从A[p..i-1]内出现‘C’,那么以A[i]为结尾的最大无重复子串，只能是A[q+1..i].

   
   

为了提高搜索某字符在字符串中上一次出现的位置，我们使用一个哈希表来存储。该表初始化所有元素为-1，提高通用性。

    int longestSubstring(string A, int n) {
        //哈希表：每个元素上次出现的位置
        int pos[256];
        for(int i=0;i<256;++i)
            pos[i]=-1;//初始-1可以统一化使用
        //以i为结尾的最大无重复串长度
        int *len=new int[n]();
        //初始化0号字符的情况
        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数组中最大值
        int max=0;
        for(int i=0;i<n;++i){
            if(len[i]>max)
                max=len[i];
        }
        delete[] len;
        return max;
    }