c++ - 最长唯一子串

Question

这个问题似乎重复了，但我发布它是因为我找不到我想要的解决方案。如果输入字符串是“abcaadafghae”，我想要第一个最长的唯一子字符串(没有重复字符)应该是“dafgh”。我得到了下面的程序来查找这个子字符串的长度，它是 5，但我想要子字符串本身作为输出。

提前致谢。

int lengthOfLongestSubstring(string s) {
  int n = s.length();
  int i = 0, j = 0;
  int maxLen = 0;
  bool exist[256] = { false };
  while (j < n) {
    if (exist[s[j]]) {
      maxLen = max(maxLen, j-i);
      while (s[i] != s[j]) {
        exist[s[i]] = false;
        i++;
      }
      i++;
      j++;
    } else {
      exist[s[j]] = true;
      j++;
    }
  }
  maxLen = max(maxLen, n-i);
  return maxLen;
}

Answer 1

假设这是一个学习练习，下面是您如何修改算法以找到最长的唯一子串。

首先确定代码中修改 maxLen 的位置.一共有三个:

• 将其设置为零的地方，
• 设置为max(maxLen, j-i)的地方, 和
• 设置为max(maxLen, n-i)的地方

替换maxLen与 maxStr ，并按如下方式使用它:

• 用对空字符串的赋值替换对零的赋值，
• 将分配替换为 max(maxLen, j-i)用支票maxStr.length() < (j-i) ，并设置 maxStr到 s 的子串来自 i , 含, 到 j , 独家
• 将分配替换为 max(maxLen, n-i)用支票maxStr.length() < (n-i) ，并设置 maxStr到 s 的子串来自 i , 含, 到 n , 独家

返回maxStr ，这就是您的答案。

Demo.