NewArenaPassword

作者：刘子祯

关键词：字符串 搜索

题目简述

给定一个字符串，长度为$n$，然后改变其中的一些字符，使前$k$个字符和后$k$个字符相同。 $1 \leq n \leq 50.$

算法1

暴力枚举每一个字符的26种形式，然后进行判断，复杂度：26^n

算法2

如果$k<=n/2$，则可以直接判断相同的字符数量即可

算法3

这道题首先要判断字符串长度和相同部分的长度。 如果$k>n/2$超过一半，则说明有重叠部分。 有重叠部分的时候就有了一个性质：假设长度为n，重叠长度为m，每隔n-m，出现的字符串都相同。 这样就枚举每一个部分，然后暴力枚举这个部分的26个字符，然后计算那个字符的代价最小。