c++ - 如何找到不同的子串？

Question

给定一个字符串和固定长度 l，我如何计算长度为 l 的不同子字符串的数量？字符集的大小也是已知的。 (记为 s)例如，给定一个字符串“PccjcjcZ”，s = 4，l = 3，然后有 5 个不同的子字符串:“PCC”； “ccj”； “cjc”； “jcj”； “jcZ”

我尝试使用哈希表，但是速度还是很慢。事实上我不知道如何使用字符大小。我做过这样的事

int diffPatterns(const string& src, int len, int setSize) {
  int cnt = 0;
  node* table[1 << 15];
  int tableSize = 1 << 15;
  for (int i = 0; i < tableSize; ++i) {
    table[i] = NULL;
  }

  unsigned int hashValue = 0;

  int end = (int)src.size() - len;

  for (int i = 0; i <= end; ++i) {
    hashValue = hashF(src, i, len);
    if (table[hashValue] == NULL) {
      table[hashValue] = new node(i);
      cnt ++;
    } else {
      if (!compList(src, i, table[hashValue], len)) {
        cnt ++;
      };
    }
  }

  for (int i = 0; i < tableSize; ++i) {
    deleteList(table[i]);
  }

  return cnt;
}

Answer 1

Hastables 很好而且实用，但请记住，如果子字符串的长度为 L，并且整个字符串的长度为 N，则算法为 Theta((N+1-L)*L) 即 Theta( NL) 对于大多数 L。请记住，仅计算哈希值就需要 Theta(L) 时间。另外可能会发生碰撞。

可以使用后缀树，并提供一个保证O(N)时间的算法(计算深度L或更大的路径数)，但实现起来比较复杂。可取之处是您可能可以找到以您选择的语言编写的现成实现。