S002 字符串构造 最长相等真前后缀 CF1029A
CF1029A - CodeForces题意：给定一个字符串 \(t\) 构造最小的一个字符串 \(s\) ，要求字符串 \(s\) 恰好有 \(k\) 个子串等于 \(t\) 。
第一眼想到的是周期。但是有的情况有重叠不能直接将 \(t\) 复制 \(k\) 份。这就不是最小了，那么如何求最小呢？
这个重叠的话与前后缀有关。如果一个字符串的前缀等于后缀，大小为 \(L\) 的话，那么这 \(L\) 部分重叠了，可以重复利用，我们只需要在后面接上 \(t\) 即可，因为前面的后缀可以当当前的前缀使用。这就是重叠。
因为要最小，所以这个问题就转化为求最长相等真前后缀。 \(L\) 大 \(n-L\) 就小，求出 \(L\) 后只需要在原串上后面加上 \((k-1)\) 个 \(t\) 。
因为数据很小可以直接 \(O(n^2)\) ，也可以使用前缀函数求出 \(\pi\) 数组， \(\pi\) 数组的 \(\pi\) 就是最长的 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:
L = i
return L
def main():
n, k = MII()
s = inp()
pi = * n
for i in range(1, n):
j = pi
while j > 0 and s != s:
j = pi
if s == s:
j += 1
pi = j
L = pi
print(s + (k - 1) * (s))
if __name__ == "__main__":
main()
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢分享，辛苦了
页:
[1]