最长不重复子串的长度最长重复子串

最长不重复子串的解法一&＃xff1a;

       设置一个辅助数据结构&＃xff08;如map&＃xff09;记录每个字符最后一次出现的位置&＃xff1b;遍历字符串中的每个字符&＃xff0c;如果在map中没有出现&＃xff0c;则不重复子串的长度&＃43;1&＃xff0c;并更新最大字符串的长度值&＃xff1b; 如果在map中已经出现过&＃xff0c;则更新当前字符在map中的位置和当前不重复子串的长度&＃xff0c;并根据更新的长度来更新最大字符串的长度&＃xff1b;这样就可以求出该字符串中的最大不重复子串的最大长度&＃xff1b;

但是最长不重复子串可能有多个&＃xff0c;如何将所有子串打印出来&＃xff1b;可以设立一个二维数组或者二维vector&＃xff0c;来存储所有不重复子字符串的长度长度和首位置&＃xff0c;然后遍历这这个数据结构打印最长不重复子串&＃xff1b;

最长不重复子串的解法二&＃xff1a;

We want to finish this task in one scan. We can maintain a hashtable to detect if we have seen any character. We start from the beginning and walk through the array until we hit a repetition, let’s say, at position i. We then have two piece of valuable information right now:

1. s[0..i-1] is a candidate of the longest substring without repetition. Therefore we can update the max length.
2. There exists a position 0<&＃61;j,  such that s[j] &＃61;&＃61; s[i]. Substring starting from j is not a candidate because it has at least one repetition: s[j] and s[i]. Any substring ended at j will be shorter than the substring s[0..i-1] so we don’t need to look at them.

Then we can remove every elements in the hashtable from 0 to j, and make the start position of next candidate to j &＃43; 1. We keep walking and repeating this process until we hit the last element.

class Solution {
public:int lengthOfLongestSubstring(string s) {unsigned int maxLen &＃61; 0;set hashtable;int candidateStartIndex &＃61; 0;for(unsigned int iter &＃61; 0; iter };

最长重复子串的解法&＃xff1a;

大方向有两个&＃xff1a;一个是后缀数组/后缀树&＃xff0c; 另外一个就是KMP算法&＃xff1b;

KMP解法&＃xff1a;遍历字符串字符i&＃xff0c;分别计算以i位置字符为首字符的字符串的next数组&＃xff0c;遍历next数组选取最大的元素&＃xff0c;更新最大重复子串的长度&＃xff1b;打印方法可以参考不重复子串的做法&＃xff1b;

http://hi.baidu.com/fangm/blog/item/58fd1a4c20a5eafdd72afcd0.html