S002 字符串构造 最长相等真前后缀 CF1029A

CF1029A - CodeForces
题意：给定一个字符串 \(t\) 构造最小的一个字符串 \(s\) ，要求字符串 \(s\) 恰好有 \(k\) 个子串等于 \(t\) 。
第一眼想到的是周期。但是有的情况有重叠不能直接将 \(t\) 复制 \(k\) 份。这就不是最小了，那么如何求最小呢？
这个重叠的话与前后缀有关。如果一个字符串的前缀等于后缀，大小为 \(L\) 的话，那么这 \(L\) 部分重叠了，可以重复利用，我们只需要在后面接上 \(t[L:]\) 即可，因为前面的后缀可以当当前的前缀使用。这就是重叠。
因为要最小，所以这个问题就转化为求最长相等真前后缀。 \(L\) 大 \(n-L\) 就小，求出 \(L\) 后只需要在原串上后面加上 \((k-1)\) 个 \(t[L:]\) 。
因为数据很小可以直接 \(O(n^2)\) ，也可以使用前缀函数求出 \(\pi\) 数组， \(\pi\) 数组的 \(\pi[n-1]\) 就是最长的 Border 。
具体代码为

1. import sys
3. Max = lambda x, y: x if x > y else y
4. Min = lambda x, y: x if x < y else y
6. input_type = 1
8. if input_type:
9.     inp = lambda: sys.stdin.readline().strip()
11.     II = lambda: int(inp())
12.     MII = lambda: map(int, inp().split())
13.     LII = lambda: list(MII())
15. else:
16.     input_data = sys.stdin.read().split()
17.     it = iter(input_data)
18.    
19.     II = lambda: int(next(it))
20.     SI = lambda: next(it)
21.    
22.     if not input_data:
23.         sys.exit()
25. def border(s):
26.     n = len(s)
27.     L = 0
28.     for i in range(1, n):
29.         if s[:i] == s[n-i:n]:
30.             L = i
31.     return L
33. def main():
34.     n, k = MII()
35.    
36.     s = inp()
38.     pi = [0] * n
40.     for i in range(1, n):
41.         j = pi[i - 1]
42.         while j > 0 and s[i] != s[j]:
43.             j = pi[j - 1]
44.         if s[i] == s[j]:
45.             j += 1
46.         pi[i] = j
47.    
48.     L = pi[n - 1]
49.    
50.     print(s + (k - 1) * (s[L:]))
52. if __name__ == "__main__":
53.     main()

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！