题目描述

题目链接

A string is said to be a palindrome if it remains same when read backwards. So, ‘abba’, ‘madam’ both are palindromes, but ‘adam’ is not.

Now you are given a non-empty string S, containing only lowercase English letters. The given string may or may not be palindrome. Your task is to make it a palindrome. But you are only allowed to add characters at the right side of the string. And of course you can add any character you want, but the resulting string has to be a palindrome, and the length of the palindrome should be as small as possible.

For example, the string is ‘bababa’. You can make many palindromes including

bababababab

babababab

bababab

Since we want a palindrome with minimum length, the solution is ‘bababab’ cause its length is minimum.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a string S. You can assume that 1 ≤ length(S) ≤ 106.

Output

For each case, print the case number and the length of the shortest palindrome you can make with S.

Sample Input

1
2
3
4
5
4
bababababa
pqrs
madamimadam
anncbaaababaaa

Sample Output

1
2
3
4
Case 1: 11
Case 2: 7
Case 3: 11
Case 4: 19

Note

Dataset is huge, use faster I/O methods.

题解

题目大意是给你n个字符串， 让你至少补多少个字母， 能使其成为回文串， 并输出补充之后的字符串的长度最短

要是不明白马拉车的实现原理， 那就给你推荐两篇博客：
博客1
博客2

就是用马拉车求包含最后一个字符的最长回文串， 那就在马拉车那里动手脚咯， 详情请看代码注释

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

char s[3 * N], str[3 * N];
int len[3 * N], l;
void init(){
    int cnt = 0;
    str[cnt++] = '$';
    for (int i = 0; i < l; i++){
        str[cnt++] = '#';
        str[cnt++] = s[i];
    }
    str[cnt++] = '#';
    l = cnt;
}

int manacher(){
    int mx = 0, id = 0;
    int ans = 0;
    len[0] = 1;
    for (int i = 1; i < l; i++){
        if (i < mx)
            len[i] = min(len[2 *id - i], mx - i);
        else
            len[i] = 1;
        while(str[i - len[i]] == str[i + len[i]]) len[i] ++;
        if (i + len[i] > mx){
            id = i;
            mx = i + len[i]; // 更新这里的时候， 不更新ans了
        }
        if (i + len[i] >= l)
        // 这是关键点， 当mx大于这个字符串长度的时候， 就说明这就是包含最后一个字符的最长回文串了
            return len[i] - 1;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s;
        l = strlen(s);
        int l1 = l;
        init();
        printf("Case %d: %d\n", i, 2 * l1 - manacher());
    }
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan