题目：求一个字符串中最长的没有重复字符的子串。
方法一：穷举法，使用2重外循环遍历所有的区间，用2重内循环检验子串是否符合“无重复字符”这一要求。其中外层循环i、j 遍历所有的下标，m、n是内层循环，检查区间[i,j]是否符合要求。空间复杂度是O(1)，时间复杂度O(N^4)。
//O(N^4)的时间复杂度 int max_unique_substring1(char * str) { int maxlen = 0; int begin = 0; int n = strlen(str); for(int i=0; i<n; ++i) for(int j=1; j<n; ++j) { int flag = 0; for(int m=i; m<=j; ++m) { for(int n=m+1; n<j; ++n) { if(str[n] == str[m]) { flag = 1; break; } } if(flag == 1) break; } if(flag==0 && j-i+1>maxlen) { maxlen = j-i+1; begin = i; } } printf("%.*s\n", maxlen, &str[begin]); return maxlen; }
方法二：对方法一的检验子串是否“无重复字符”进行改进，使用hash表记录字符是否出现过。
//O(N^2)的时间复杂度 int max_unique_substring2(char * str) { int i,j; int begin; int maxlen = 0; int hash[256]; int n = strlen(str); for(i=0; i<n; ++i) { memset(hash,0,sizeof(hash)); hash[str[i]] = 1; for(j=i+1; j<n; ++j) { if(hash[str[j]] == 0) hash[str[j]] = 1; else break; } if(j-i > maxlen) { maxlen = j-i; begin = i; } } printf("%.*s\n", maxlen, &str[begin]); return maxlen; }
方法三：对字符串“axbdebpqawuva”构造下表：
表中，字符串有3个‘a’，有2个‘b’，其余为单一字符。next[]记录了下一个与之重复的字符的位置，如str[0]=str[8]=str[12]=‘a’，这时next[0]=8，next[8]=12，next[12]=13，其余同理。值得注意的是，对于没有重复字符的，next[]存储字符结束符‘\0’的下标，即13。
这里，first[i]表示i之后，第一次出现重复字符的那个位置。例如，str[0]之后，第一次出现的重复字符是str[5]=‘b’，当然，从str[1]，str[2]开始也是一样。而从str[3]开始，要到str[12]才出现重复字符‘a’。可以证明，从str[i]起的最长符合要求的长度为first[i]-i，区间为[i,first[i]-1]由此得解。上述最长串是当i=3时，first[i]-i=12-3=9。结果最长无重复子串为“debpqawuv”。
//O(N)的时间复杂度 int max_unique_substring3(char * str) { int maxlen = 0; int begin = 0; int n = strlen(str); int * next = (int*)malloc(sizeof(int)*n); //next[i]记录了下一个与str[i]重复的字符的位置 int * first = (int*)malloc(sizeof(int)*(n+1)); //first[i]记录str[i]后面最近的一个重复点 int hash[256]; memset(hash,n,sizeof(hash)); first[n] = n; for(int i=n-1; i>=0; i--) { next[i] = hash[str[i]]; hash[str[i]] = i; if (next[i] < first[i+1]) first[i] = next[i]; else first[i] = first[i+1]; //生成first[]表，复杂度是O(N)的 } for(int i=0; i<n; i++) { if (first[i]-i > maxlen) { maxlen = first[i]-i; begin = i; } } free(first); free(next); printf("%.*s\n", maxlen, &str[begin]); return maxlen; }
另一种实现：visit[]记录每次字符出现的位置，当出现重复字符时，通过两次重复字符的位置得到新的子串的长度，但是，每次只通过重复字符的位置得到新的子串的长度是不对的，还需要考虑上一次子串的开始位置。
//O(N)的时间复杂度 int max_unique_substring3(char * str) { int visit[256]; memset(visit, -1, sizeof(visit)); int n = strlen(str); int maxlen = 0; visit[str[0]] = 0; int curlen = 1; int last_start = 0; int begin; for(int i=1; i<n; ++i) { if(visit[str[i]] == -1) { ++curlen; visit[str[i]] = i; // 记录字符出现的位置 } else { if(last_start <= visit[str[i]]) { curlen = i - visit[str[i]]; last_start = visit[str[i]] + 1; //跟新下一次开始的位置 visit[str[i]] = i; // 更新最近重复位置 } else { ++curlen; } } if(curlen > maxlen) { maxlen = curlen; begin = i + 1 - maxlen; } } printf("%.*s\n", maxlen, &str[begin]); return maxlen; }
方法四：使用后缀数组
对这个字符串构造后缀数组，在每个后缀数组中，寻找没有重复字符的最长前缀，最长的前缀就是要找的子串。
//得到字符串最长的无重复的前缀长度 int longestlen(char * p) { int hash[256]; int len = 0; memset(hash,0,sizeof(hash)); while (*p && !hash[*p]) { hash[*p] = 1; ++ len; ++ p; } return len; } //使用后缀数组解法 int max_unique_substring4(char * str) { int maxlen = -1; int begin = 0; char *a[999]; int n = 0; while(*str != '\0') { a[n++] = str++; } for (int i=0; i<n; i++) { int temlen = longestlen(a[i]); if (temlen > maxlen) { maxlen = temlen; begin = i; } } printf("%.*s\n", maxlen, a[begin]); return maxlen; }
