回文串拼接 - 算法题解

时间限制: 3000MS\n\n内存限制: 589824KB\n\n题目描述:\n\n我们称一个字符串为回义串，当且仅当这个串从左往右和从右往左读是一样的。例如，aabbaa、a、abcba，而ab、ba、abc不是回文串。注意单个字符也算是回文串。\n\n现在，给你一个长度为n的字符串 S，接下来需要将这个串重新排列，组成一个新的字符串 T。首先，T一开始为空，之后进行如下操作：从左往右开始，剪切 S 中开头k个字符构成的子串，如果该子串是一个回文串，就将其拼接在T的前面；否则，将其拼接在T的末尾，其中k是一个给定的参数。\n你需要输出最后T是多少？\n\n输入描述：\n\n第一行两个正整数 n,k (1<=n，k<=100000)，其中k是n的因子。\n第二行输入字符串 S。该字符串仅由小写英文字母组成。\n\n输出描述：\n\n输出一行一个字符串，表示T。\n\n思路：\n\n首先，我们需要找到所有的回文串，然后按照给定的顺序将它们拼接起来。\n\n对于一个长度为n的字符串，我们可以将其分成n/k个长度为k的子串。我们可以从左往右遍历字符串，每次取出k个字符，判断它是否是回文串。如果是回文串，我们就将它拼接在T的前面；否则，将它拼接在T的末尾。\n\n具体实现：\n\n1. 读入n和k，并初始化一个空串T。\n\n2. 读入字符串S。\n\n3. 从左往右遍历字符串S，每次取出k个字符。\n\n4. 判断取出的k个字符是否是回文串。如果是回文串，就将它拼接在T的前面；否则，将它拼接在T的末尾。\n\n5. 输出T。\n\n代码实现如下：\n\npython\nn, k = map(int, input().split())\nS = input()\n\nT = ''\nfor i in range(0, n, k):\n substring = S[i:i+k]\n if substring == substring[::-1]:\n T = substring + T\n else:\n T += substring\n\nprint(T)\n\n\n复杂度分析：\n\n由于需要遍历字符串S，并对每个长度为k的子串进行判断，所以时间复杂度为O(n/k * k) = O(n)。\n\n空间复杂度为O(n)，用于存储结果T。