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

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

为了使每个单个(两个或多个字符)子字符串至少具有与零一样多的子字符串,可以没有连续的零 - 实际上,每对零之间至少需要两个零.那是因为字符串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标志.您可以在分析中发现其他人,但这是一个良好的开端,并允许您进一步分摊检查成本.