URAL 1354. Palindrome. Again Palindrome

Author: 2015-11-17

ACM

, , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1354

1354. Palindrome. Again Palindrome

Time limit: 1.0 second
Memory limit: 64 MB

 

A word is the nonempty sequence of symbols a1a2…an. A palindrome is the word a1a2…an that is read from the left to the right and from the right to the left the same way (a1a2…an = anan−1…a1). If S1 = a1a2…an and S2 = b1b2…bm, then S1S2= a1a2…anb1b2…bm. The input contains some word S1. You are to find a nonempty word S2 of the minimal length thatS1S2 is a palindrome.

Input

The first input line contains S1 (it may consist only of the Latin letters). It’s guaranteed that the length of S1 doesn’t exceed 10000 symbols.

Output

S1S2.

Samples

input output 
No

NoN

OnLine

OnLineniLnO

AbabaAab

AbabaAababA
Problem Author: Denis Nazarov
Problem Source: USU Junior Championship March’2005

2. 思路

给出一个字符串S1，寻找一个最短的非空字符串S2，使得S1S2构成回文，输出S1S2。

找出S1中包含S1结尾的最长回文子序列，S1中的剩余部分即为所求。如AbabaAab中，包含结尾的最长回文子序列为baAab，剩余部分Aba即为S2。注意题目要求S2非空，如果S1本身就是回文，依旧需要找到一个非空的S2。

3. 代码

代码中令*start = str + 1 ，跳过了第一个字符，防止当S1本身是回文时得到空的S2。

#include <cstdio>
#include <cstring>

const int MAX_LENGTH = 20001;

void solveP9c_PalindromeAgainPalindrome();
bool isPalindrome(char *start, char *end);

int main() {
    solveP9c_PalindromeAgainPalindrome();
    return 0;
}

char str[MAX_LENGTH];
void solveP9c_PalindromeAgainPalindrome() {
    scanf("%s", str);

    int len = strlen(str);
    
    // S2 must not be empty.
    char *start = str + 1, *end = str + len - 1;
    while (!isPalindrome(start, end) && (end - start >= 0)) {
        ++start;
    }

    printf("%s", str);
    while (start - str > 0) {
        printf("%c", *--start);
    }
    printf("\n");
}

bool isPalindrome(char *start, char *end) {
    while (end - start >= 0) {
        if (*start != *end) {
            return false;
        }
        ++start;
        --end;
    }
    return true;
}