给出一个字符串，找出这个字符串中最长连续的而且没有重复字符的子串，并返回它的长度。例如，对于字符串“BDEFGABEF”最长连续且没有重复字符的子串可以是“DEFGAB”或者“DEFGAB”，长度是6。对于字符串“BBBB”，它满足要求的字串的长度是1，即“B”。
首先分析一下，对于给定长度的字符串，它一共有多少个字串呢？ 子串数 = 长度为1的子串数+长度为2的子串数+ 。。。+长度为n的子串数 = （n + 1） * n / 2
。 对于每个子串，在O（n）的时间内遍历它，看它是否有重复的字符出现。计算（n + 1） * n / 2个子串共需要花费的时间是O（n^3）。对于长度很长的字符串，这样的计算时间显然不行，下面介绍一种O（n）时间就可以搞定的算法。这个算法首先增加辅助空间，visited[256]， 其中visited[i]表示ascii为i的字符出现的索引位置。因为索引都是从0开始的，所有把visited的所有值都初始化为0，接下来具体算法：
1，维护变量max_len表示满足要求的最大值，cur_len表示当前计算的没有重复字符的子串的长度，pre_index表示当前索引处的字符在之前出现过的位置，-1表示没有出现过。
2，对于每个当前遍历的字符，我们检查它在之前已经处理过的部分，也就是当前字符之前的所有字符中是否包含当前字符，如果没有出现过，那么我们就将cur_len++,以增加当前最长连续而且没有重复字符的子串的长度。
3，如果当前字符（即i索引处）的字符在之前出现过，出现的索引值是pre_index， 那么要做判断，判断pre_index处的字符是否在当前最长连续且没有重复字符串中，如果不在那么就将cur_len++，如果在的话那么就要首先判断max_len 与cur_len之间的关系，然后根据他们的关系来决定是否改变max_len，之后还得处理cur_len的值，因为已经出现了重复字符了，这样cur_len就得改变，改变成当前索引出的字符到pre_index处下一个字符位置差值，这样做，当前满足条件的子串才不会有重复的字符。
下面对上面的算法举个例子，GEEKSFORGEEKS：
1，
这个时候因为之前没有G，所以cur_len++，记录G出现位置。
2，
3，
之前E出现过，而且之前cur_len=2，所以得减去之前E出现的索引，用max_len记录遍历过的最大长度，之前max_len是0.
4，
5，
6，
7，
8，
9，
10，
剩下的大家有兴趣自己画图吧，下面给出代码：
#include<iostream>
#include<string>
using namespace std;
const int CH_NUM = 256;
int longest_non_repeat_str(const char* s) {
int i;
int pre_index = -1;
int length = strlen(s);
int max_len = 0;
int cur_len = 1;
int visited[CH_NUM] = {-1};
visited[s[0]] = 0; // first char has been visited
for (i = 1; i < length; i++) {
pre_index = visited[s[i]];
if (-1 == pre_index || i - cur_len > pre_index) {
cur_len++;
} else {
if (cur_len > max_len)
max_len = cur_len;
cur_len = i - pre_index;
}
visited[s[i]] = i;
}
if (cur_len > max_len)
max_len = cur_len;
return max_len;
}
int main(int argc, char* argv[]) {
char s[] = "geeksforgeeks";
int rst = longest_non_repeat_str(s);
cout << rst << endl;
cin.get();
return 0;
}
