特殊字符串序列的时间复杂度

Question

问题:存在一个特殊的字符串序列，其中第n个字符串等于:前一个字符串+ "0"+前一个字符串

S1 = 1, S2 = 101, S3 = 1010101, S4 = 10101010101010101

我想问是什么让k的最低时间复杂度的第n个字符串。我可以这样做而不查找字符串序列中的每个先前元素吗?

Answer 1

我认为当你使用1和0时很难看到一个模式，所以我们用字母代替。

S1 = abc S2 = abc-d-abc S3 = abcdabc-d-abcdabc

模式现在更明显了。总有S1 + d + S1 + d +。+ S1。

长度为S1。长度* n + (n - 1).图案长度为4。所以长度并不重要,k字符(S1 + d) [k % 4] k & lt;长度。

如果不生成新的字符串，时间复杂度为0(1)。