时间戳

首页 > 解决方案 > 计算形成字符串的连续子串的有序可能不连续子串的数量

algorithm - 计算形成字符串的连续子串的有序可能不连续子串的数量

问题描述

假设 S(N) 是长度为 N 的字符串“012012012...”，其中重复“012”直到我们有 N 个字符。

对于任何给定的 N，通过从字符串中按顺序选择可能不连续的字母来计算形成连续子字符串的方式的数量。

例如，对于 N = 5，我们有 S(N) = "01201"

连续子串和计数：

'0', 2
'1', 2
'2', 1
'01', 3 (the two consecutive '01' along with the first and last character of '01201').
'12', 1
'20', 1
'012', 1
'120', 1
'201', 1
'0120', 1
'1201', 1
'01201', 1

Total: 16

我们如何才能有效地计算任意 N？我将发布我的最佳答案作为解决方案。

注意这个问题最初来自Cococino223，但措辞不佳，在修复之前被删除。

标签： algorithmdynamic-programming

解决方案

假设 f(n) 是 n 的计数，f(n, k) 是在 {0,1,2} 中以 k 结尾的那些子串的 n 的计数。

N  f(n, 0)  f(n, 1)  f(n, 2)  f(n)
0       0        0        0     0      
1       1        0        0     1      
2       1        2        0     3      
3       1        2        3     6      
4       5        2        3    10       
5       5        8        3    16       
6       5        8       12    25        
7      18        8       12    38        
8      18       27       12    57          
9      18       27       40    85          
10     59       27       40    126           
11     59       87       40    186

方法论： f(n, k) 仅在第 n 个字符串以 k 结尾时才会改变。在这种情况下：

f(n, k) = f(n-1, k) + f(n-1, k') + 1
Where k' is the predecessor of k in '012' with wraparound.

E.g., f(6,2) = 12 = f(5,2) + f(5,1) + 1

这里的直觉是，我们有所有不使用最新字母 (f(n-1, k)) 的以 k 结尾的方式，所有使用最新 k 的方式，必须等于所有方式使用序列中的前一个字母，并在末尾添加 k (f(n-1, k'))，以及单例新 k (+1)。

这是线性时间，恒定记忆。

-- 更新 -- 如果你读到变化的数字：1、2、3、5、8、12、18、27、40、59、87、128、188、276、405、594、871，这是OEIS序列 A077868。

- 更新 - 

[a, b, c, 1] * [0, 0, 1, 0] = [b, c, a+c+1, 1]
               [1, 0, 0, 0]
               [0, 1, 1, 0]
               [0, 0, 1, 1]

调用 M 上面的方阵。然后我们可以用 M 来计算 k 的连续值。例如，[12, 18, 27, 1] * M = [18, 27, 40, 1]

我们可以使用它通过反复对矩阵求平方来在对数时间内求解 f(n)。

E.g. M^8 = [4,   6,  9, 0]
           [3,   4,  6, 0]
           [6,   9, 13, 0]
           [12, 18, 27, 1]

[0, 0, 0, 1] * M^8 = [12, 18, 27, 1]
12 + 18 + 27 = 57 = f(8)

f(n) 是 M^n 的底行的前三个元素的总和。

所以 f(n) 可以在对数时间内计算，但由于矩阵 mult 相当昂贵，这仅对相对较大的 n 有意义。请注意，这适用于不是 2 的幂的数字，方法是将 2 的适当幂的矩阵相乘。例如 13 = 1101，因此我们将 (M^1) (M^4) (M^8) 相乘。

推荐阅读