S002构造最长前后缀CF1029A，如何为？
摘要：CF1029A - CodeForces 题意：给定一个字符串 (t) 构造最小的一个字符串 (s) ，要求字符串 (s) 恰好有 (k) 个子串等于 (t) 。 第一眼想到的是周期。但是有的情况有重叠不能直接将 (t
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 。
具体代码为
import sys
Max = lambda x, y: x if x > y else y
Min = lambda x, y: x if x < y else y
input_type = 1
if input_type:
inp = lambda: sys.stdin.readline().strip()
II = lambda: int(inp())
MII = lambda: map(int, inp().split())
LII = lambda: list(MII())
else:
input_data = sys.stdin.read().split()
it = iter(input_data)
II = lambda: int(next(it))
SI = lambda: next(it)
if not input_data:
sys.exit()
def border(s):
n = len(s)
L = 0
for i in range(1, n):
if s[:i] == s[n-i:n]:
L = i
return L
def main():
n, k = MII()
s = inp()
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
L = pi[n - 1]
print(s + (k - 1) * (s[L:]))
if __name__ == "__main__":
main()