回文串

[题目链接](https://www.nowcoder.com/practice/feb7cc6085e0487dab796e00e53ee772)

思路

本题是一道模拟题。按照题意，依次从字符串 $S$ 的开头取出长度为 $k$ 的子串，判断其是否为回文串，然后决定拼接到 $T$ 的前面还是后面。

模拟过程

将字符串 $S$ 从左到右每 $k$ 个字符分成一组，共得到 $n / k$ 个子串。
对每个子串判断是否为回文串：

- 如果是回文串，将其拼接到 $T$ 的前面（prepend）。

- 如果不是回文串，将其拼接到 $T$ 的后面（append）。

输出最终的 $T$ 。

使用双端队列（deque）可以方便地实现头部和尾部的插入操作。最后将队列中的所有子串按序拼接即为答案。

样例演示

$S = \texttt{ababaacbaccc}$ ， $k = 3$ ，分成 4 个子串：

子串	是否回文	操作	$T$
`aba`	是	前插	`aba`
`baa`	否	后插	`aba` + `baa`
`cba`	否	后插	`aba` + `baa` + `cba`
`ccc`	是	前插	`ccc` + `aba` + `baa` + `cba`

最终 $T = \texttt{cccababaacba}$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    deque<string> dq;
    for (int i = 0; i < n; i += k) {
        string sub = s.substr(i, k);
        string rev = sub;
        reverse(rev.begin(), rev.end());
        if (sub == rev) {
            dq.push_front(sub);
        } else {
            dq.push_back(sub);
        }
    }

    string t;
    for (auto& part : dq) {
        t += part;
    }
    cout << t << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        String s = sc.next();

        Deque<String> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i += k) {
            String sub = s.substring(i, i + k);
            String rev = new StringBuilder(sub).reverse().toString();
            if (sub.equals(rev)) {
                dq.addFirst(sub);
            } else {
                dq.addLast(sub);
            }
        }

        StringBuilder t = new StringBuilder();
        for (String part : dq) {
            t.append(part);
        }
        System.out.println(t.toString());
    }
}

复杂度分析

时间复杂度： $O(n)$ ，遍历字符串一次，每个子串的回文判断耗时 $O(k)$ ，总共 $n/k$ 个子串，故总计 $O(n)$ 。
空间复杂度： $O(n)$ ，存储双端队列中的子串和最终结果字符串。