小园香径独徘徊

Luogu

IDLGP9348

Time1000ms

Memory512MB

DifficultyP7

字符串贪心洛谷原创后缀自动机 SAMO2优化后缀数组 SA洛谷月赛

有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串： 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头； 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾； 1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。 a3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。 ## Input **本题有多组测试数据。** 第一行一个整数 $Q$，表示测试数据组数。对于每组测试数据，一行一个字符串 $S$。 ## Output 对于每组测试数据，一行一个字符串，表示可以构成的字典序最小的 $T$。 [samples] ## Background 徘徊在一条幽深的小径上，拾起记忆的碎片，将它们放入两个长长的口袋中。将它们收集完倒出来后，会拼成什么样的故事呢？ ## Note **【样例 1 解释】** - 对于 $\texttt{ababdca}$，依次进行第 $1,2,1,2,2,2,1$ 种操作，即可得到 $\texttt{aaabbdc}$。 - 对于 $\texttt{dcbcadb}$，依次进行第 $1,1,1,2,3,1,2$ 种操作，即可得到 $\texttt{abbcdcd}$。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（5 points）：$S$ 由至多两种字符构成。 - Subtask 2（10 points）：$\sum |S|\le 12$。 - Subtask 3（15 points）：$\sum |S|\le 100$。 - Subtask 4（25 points）：$\sum |S|\le 3\times 10^3$。 - Subtask 5（20 points）：$\sum |S|\le 2\times 10^5$。 - Subtask 6（25 points）：无特殊限制。对于 $100\%$ 的数据，$1\le Q\le 3\times 10^5$，$1\le |S|\le 10^6$，$1\le \sum |S|\le 2\times 10^6$，$S$ 仅由小写字母构成。

Samples

Input #1

2
ababdca
dcbcadb

Output #1

aaabbdc
abbcdcd

API Response (JSON)

{
  "problem": {
    "name": "小园香径独徘徊",
    "description": {
      "content": "有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串： 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头； 1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾； 1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。 a3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9348"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有两个字符串 $S,T$，一开始给定 $S$，$T$ 为空串。每次你可以执行以下三种操作，直到 $S$ 变为空串：\n\n1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的开头；\n1. 删去 $S$ 的第一个字符，并将这个字符插入 $T$ 的末尾；\n1. 删去 $S$ 的最后一个字符，并将这个字符插入 $T$ 的开头。\n\na3 想知道，$S$ 变为空串后，可以构成的字典序最小的 $T$。\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments