该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P15896 [TOPC 2025] Palindromic Distance

题目描述

两个字符串 $u$ 和 $v$ 之间的编辑距离，是指将 $u$ 转换为 $v$ 所需的最少编辑操作次数。可以对字符串应用三种编辑操作：插入一个字符、删除一个字符，以及将某个字符替换为另一个不同的字符。

例如，我们可以通过四次替换将 hello 转换为 world，因此编辑距离至多为 4。通过两次替换和一次插入可以将 wally 转换为 walter，因此编辑距离至多为 3。计算两个字符串之间的编辑距离是一个经典问题，具有广泛的应用。

当前的任务是计算一个字符串到 最近的回文串 的编辑距离。回文串是指正反读起来相同的字符串，例如 madam。

字符串 hello 到最近回文串的编辑距离仅为 2：我们可以通过两次编辑操作将 hello 转换为 ollo、hllh 或 ellle。

请编写一个程序，找出一个单词到最近回文串的距离。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$，接下来是每个测试用例的描述。

每个测试用例只有一行，包含一个单词 $w$，仅由小写字母组成。

输出格式

对于每个测试用例，输出输入单词 $w$ 与其最近回文串之间的编辑距离。

输入输出样例 #1

输入 #1

6
aaaaba
hello
palindrome
abba
x
bababac

输出 #1

1
2
5
0
0
1

说明/提示

• $1 \le t \le 200$
• 单词 $w$ 的长度至少为 1。
• 保证所有测试用例中单词 $w$ 的长度之和不超过 $3000$。

翻译由 DeepSeek V3.2 完成