string - 试图找到一个更有效的算法

Question

二进制字符串是每个字符为“0”或“1”的字符串。一个二进制字符串 S 是好的当且仅当对于 S 的每个子字符串，“0”的数量小于或等于“1”的数量。

字符串S的子串可以通过从S的开头删除几个(或零个)字符和从S的结尾删除几个(或零个)字符，从S中至少留下两个字符来获得。例如，如果S = "abcdfab"，则"abcd"、"fab"、"bcdfa"、"abcdfab"是S的子串，而"abab"、""、"d"、"adcdab"不是S的子串。

我想找出一种方法来检查长度为 N 的二进制字符串是否正确。

天真的方法是检查这个二进制字符串的每个子字符串，其时间复杂度为 O(N^2)，是否有一种算法可以具有 O(N) 或更好的时间复杂度？

Answer 1

为了使每个单个(两个或更多字符)子字符串至少具有与零一样多的 1，不能有连续的零 - 事实上，您至少需要 两个每对零之间的一个。那是因为字符串 010 无效，但是0110 的没有两个字符的子字符串违反了您的约束。

所以算法是:

set oneCount to 2 # Zero at start of string is okay.
for each character ch in string:
    if ch is 0:
        if oneCount is less than 2:
            generate error
        set oneCount to 0
    else:
        increment oneCount

这实际上是 O(n) 时间，但您实际上可以通过分摊成本做得更好。由于在检查之前可能会对字符串进行多次修改操作，因此您可以推迟检查以降低摊销成本。

我的意思是缓存字符串的有效性，这样，如果您在没有修改它的情况下进行检查，只需返回缓存的值而不是重新检查。这是最粗略的摊销水平，但可能会单独带来改进:

define string = "", dirty = false, cachedValidity = true

define isValid():
    if dirty:
        cachedValidity = true
        set oneCount to 2
        for each character ch in string:
            if ch is 0:
                if oneCount is less than 2:
                    cachedValidity = false
                    exit for loop
                set oneCount to 0
            else:
                increment oneCount
    dirty = false
    return cachedValidity

然后您只需确保对字符串的任何操作都将 dirty 设置为 true，这在面向对象语言中实际上非常容易。

为了进一步优化，您不需要为所有 操作将dirty 设置为true，这实际上取决于您在做什么。字符串有效性在(至少)以下条件下不会改变:

1. 如果您将一个插入到另一个旁边。
2. 如果您删除一个介于其他两个之间的一个。
3. 如果你在四个连续的中间插入一个零。

这些操作都不会影响有效性，因此它们不应设置 dirty 标志。您可能会在分析中发现其他内容，但这是一个良好的开端，可以让您进一步分摊检查成本。