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 sysMax = lambda x, y: x if x > y else y
Min = lambda x, y: x if x < y else yinput_type = 1if 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 = 0for i in range(1, n):if s[:i] == s[n-i:n]:L = ireturn Ldef main():n, k = MII()s = inp()pi = [0] * nfor 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 += 1pi[i] = jL = pi[n - 1]print(s + (k - 1) * (s[L:]))if __name__ == "__main__":main()