给定条件下N个长度内的所有可能序列

Question

例如，我们得到长度为5（n=5）的字符串“Number”，它由从1到a的所有数字组成（数字可以重复，但从1到a的所有数字都必须包含在字符串中，并且字符串的长度必须为n）。假设a=2并使用先前给定的条件生成示例性数字（或者更确切地说是数字序列），假设它是长度为5并由1和2组成的“12211”。现在让我们假设我们需要找到一个算法，该算法将在我们的字符串“Number”中找到所有可能的数字序列，其中每个序列都是“Number”的子字符串，每个序列具有不同的长度，可能只包含任何数字的一次出现。

对于我们的示例“12211”，我们可以说有7个序列：

1.    "1"
2.    "12"
3.    "2"
4.    "2"
5.    "21"
6.    "1"
7.    "1"

结果将是“7”。

另一个清晰的例子：对于“Number”=“123452”和b=5（数字为1,2,3,4,5）可能的序列是：

1.    "12345"
2.    "1234"
3.    "123"
4.    "12"
5.    "1"
6.    "2345"
7.    "234"
8.    "23"
9.    "2"
10.   "3452"
11.   "345"
12.   "34"
13.   "3"
14.   "452"
15.   "45"
16.   "4"
17.   "52"
18.   "5"
19.   "2"

结果将是“19”。

你对快速算法有什么想法吗？我想出的那个太慢了（比较每个数字）。

Answer 1

int count(std::string seq, int len) {
   int sum = 0;
   bool elem[256] = {0};
   int i = 0, j = 0;
   while ( i < len ) {
      while ( !elem[seq[j]] && j < len) {
         elem[seq[j]] = true;
         j++;
      }
      sum += j - i;
      elem[seq[i]] = false;
      i++;
   }
   return sum;
}

我想不出比这更有效的解决方案了。祝你好运

Answer 2

看看最长的常见子序列问题，查看“读取所有LCS”部分，并巧妙地使用矩阵，您将获得所需的所有内容。

Answer 3

将布尔表作为一个集合（在第n个元素中为true表示n在实际间隔中）

现在很简单。您应该遍历数组并扩展间隔，当您找到重复的元素时，您只需移动间隔的开始，直到您到达唯一序列。

一些更好解释的代码：

unsigned long long number_of_seq(string seq) {
  set<char> in_use; //Can be some O(1) set, pointless
  unsigned long long result = 0ULL;
  //p - begin of actual interval
  //q - end of this interval
  for(size_t p = 0, q = 0; q < seq.size();) {
       while(in_use.count(seq[q]) != 0) { //While: add seq[q] makes interval not unique
            in_use.erase(seq[p]);
            ++p; //move begin of interval
        }
       in_use.insert(seq[q]);
       ++q;
       result += q - p; //add size of interval
   }
  return result;
 }

您应该添加任意间隔的大小，因为您只需在末尾添加新元素，所有子字符串都是正确的（没有两个相同的字符），并且所有没有新字符的子字符串都会被考虑。它是seq[0:q]和seq[q]中最大的唯一子串，所以它是正确的。