问题描述

对于一个字符串 ， 表示的子串为 的连接。类似于一个半闭半开的区间。

简称 , 是一个长度为的的子序列 ，使得 ，且最大。

给定 ，求 。假设 的长度为 。

思路

基于 的做法

• 对于任意的 ，假设 为 和 的最长公共子序列。那么两个 连在一起可以形成一个可能的解。
• 枚举所有可能的解，其中的最长的解就是的 。
  因为求 的复杂度为 ，因此该方法的复杂度为 。

复杂度为 的做法

一些定义

• 定义 ，也就是 与 的最长公共字串的长度。
• 那么
• 定义
• 定义

该方法通过找 之间的规律，从而得到 之间的关系，推导出复杂度为 的算法。

具体的规律为（例子）：

• 下面的 个图分别是 时， 与 以及 的取值情况。可以发现，从每一行上看，的值总是分布在一个连续的区间内的，因此可以通过一个序列 对 建模（通过便可以求出 ）。
• 的性质为：
  1. 如果
     1. 如果不存在 ，
     2. 否则，
  2. 否则
     1. 如果不存在 ,
     2. 否则，
• 通过上述性质，就可以在 的复杂度下求出 ，从而求出 和
• 上述方法能够求出的长度，如果要还原出具体的 字符串，可以先找到最大的 ，假设是 ，通过求 的方式就求出具体的

k=4 k=5 k=6 k=7 k=8

---

上述性质的证明方法：

对于 ：

1. 如果，那么
2. 如果，那么
3. 那么
   证明方法：
   • 如果 ，那么 ，此时
   • 如果 ，那么

对于 ：

1. 如果 ，那么：

   • 令 ，
   • 则有

2. 否则，令 ，

   • 因为
   • 所以
   • 因此

利用上述推导，可以得出如下结论

1. 考虑为0 且 为 1的条件：
   • 且 ( 或 )
2. 考虑为1 且 为 0的条件：
   • 或
3. 利用上面两条性质，就可以得出example中的推论。

Demo 代码实现

验证代码，用于认证上述推论的正确性

def call_lts(s):
    n = len(s)
    pf = [0 for _ in range(n + 1)]
    f = [0 for _ in range(n + 1)]
    for k in range(1, n + 1):
        last_pos = dict()
        for i in range(1, k):
            if s[k-1] in last_pos:
                if s[i-1] == s[k-1]:
                    f[i] = max(pf[last_pos[s[k-1]]+1:i+1])
                else:
                    f[i] = max(pf[last_pos[s[k-1]]+1:i])
            else:
                if s[i-1] == s[k-1]:
                    f[i] = k - 1
                else:
                    f[i] = pf[i]

            last_pos[s[i-1]] = i - 1
        f, pf = pf, f
        print(pf) 


if __name__ == '__main__':
    call_lts('ABCABCAB')
    print('---')
    call_lts('BABBCA')

的实现，使用单调双端队列优化

from queue import deque

class OrderedDeque:

    def __init__(self, ref):
        self.data = deque()
        self.ref = ref
    
    def add(self, idx):
        while len(self.data) > 0 and self.ref[self.data[len(self.data)-1]] <= self.ref[idx]:
            self.data.pop()
        self.data.append(idx)
    
    def remove(self, idx):
        while len(self.data) > 0 and self.data[0] < idx:
            self.data.popleft()
    
    def biggest(self):
        return self.ref[self.data[0]]


def call_lts(s):
    n = len(s)
    pf = [0 for _ in range(n + 1)]
    f = [0 for _ in range(n + 1)]
    for k in range(1, n + 1):
        last_pos = dict()
        q = OrderedDeque(pf)
        for i in range(1, k):
            if s[k-1] in last_pos:
                q.remove(last_pos[s[k-1]]+1)
                if s[i-1] == s[k-1]:
                    q.add(i)
                    f[i] = q.biggest()
                else:
                    f[i] = q.biggest()
                    q.add(i)
            else:
                if s[i-1] == s[k-1]:
                    f[i] = k - 1
                    q.add(i)
                else:
                    f[i] = pf[i]
                    q.add(i)

            last_pos[s[i-1]] = i - 1
        f, pf = pf, f
        print(pf) 

    ans = 0
    for i in range(1, n + 1):
        update = 0
        for j in range(1, i+1):
            if pf[j] >= i:
                update += 1
        if update > ans:
            ans = update
    return ans


if __name__ == '__main__':
    print(call_lts('ABCABCAB'))
    print('---')
    print(call_lts('BABBCA'))

参考文献

1. Kosowski A. An efficient algorithm for the longest tandem scattered subsequence problem[C]//International Symposium on String Processing and Information Retrieval. Springer, Berlin, Heidelberg, 2004: 93-100.