题目描述

题目链接

One day, sailormoon girls are so delighted that they intend to research about palindromic strings. Operation contains two steps:
First step: girls will write a long string (only contains lower case) on the paper. For example, “abcde”, but ‘a’ inside is not the real ‘a’, that means if we define the ‘b’ is the real ‘a’, then we can infer that ‘c’ is the real ‘b’, ‘d’ is the real ‘c’ ……, ‘a’ is the real ‘z’. According to this, string “abcde” changes to “bcdef”.
Second step: girls will find out the longest palindromic string in the given string, the length of palindromic string must be equal or more than 2.

Input

Input contains multiple cases.
Each case contains two parts, a character and a string, they are separated by one space, the character representing the real ‘a’ is and the length of the string will not exceed 200000.All input must be lowercase.
If the length of string is len, it is marked from 0 to len-1.

Output

Please execute the operation following the two steps.
If you find one, output the start position and end position of palindromic string in a line, next line output the real palindromic string, or output “No solution!”.
If there are several answers available, please choose the string which first appears.

Sample Input

1
2
b babd
a abcd

Sample Output

1
2
3
0 2
aza
No solution!

题解

题意:

  1. 一开始输入的字母起得是变换作用， 比如， 若输入b， 就把原来子串所有字母减一， 若输入z 就把所有字母加一。 当着这个条件最后输出的时候变换一下就行， 不用把整个串变换。
  2. 找出最长回文串， 若长度相同只取最先出现的。
    要是不明白马拉车的实现原理， 那就给你推荐两篇博客：
    博客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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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, indx;
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];
            if (ans < len[i]){// 注意这里是 小于，取得是第一次出现的  若是小于等于， 就是取最后一次出现的
                ans = len[i];
                indx = i; // 记录最长回文串的中心位置， 这是str的！！！， 用来输出该回文串所在的位置
            }
        }
    }
    return ans - 1;
}

int main() {
    char c;
    int L, R;
    while(~scanf("%c %s", &c, s)){
        getchar();  // 加个getchar() 吃回车还是啥的巴拉巴拉  这个做的时候具体看看吧
//        cout << c << " " << s << "!!!!!\n";
        l = strlen(s);
        init();
        l = manacher();
        if (l <= 1)
            puts("No solution!");
        else{
            L = indx - l + 1;//这是最长回文串 str的左边界
            R = indx + l - 1;//这是最长回文串 str的右边界， 自己画画图就可以得到
            printf("%d %d\n", L / 2 - 1, R / 2 - 1); // 这是str的坐标y 和 s的坐标 x 满足的关系 y = 2 * (x + 1), 具体的关系式还是要看你的init()
            for (int i = L; i <= R; i += 2){
                printf("%c", 'a' + (str[i] - c + 26) % 26); // 这是一个取余处理 ， 为什么这样可以呢， 请读者深思~
            }
            putchar(10);
        }
    }
    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan