UVa 257 - Palinwords

#字符串 #回文串
Published on 2015-11-29

题目地址

描述

问一堆单词中，哪些是 palinword 并输出。
palinword 的定义为，包含两个不同的回文子串，并且要求回文子串不能互相包含。例如 aaa 和 aaaa 只算一个。

规模

单个单词长度 l<=255 l <= 255 。

样例输入

MOEILIJKHEDEN INVOER
VERNEDEREN
AMUMA AMAMA MUMMUM
AMATRAMA AAAA
ABATRABAR
DUMMY
WORDS

样例输出

MOEILIJKHEDEN
VERNEDEREN
AMAMA
MUMMUM

分析

说实话这题有点类似脑筋急转弯，，， 回文串有两种，一种是奇回文，形式为 SXSSXS。一种是偶回文，形式为 SSSS。
既然题目说不能互相包含，那么我们只考虑两种基本回文串，长度为 33 的奇回文，长度为 44 的偶回文。因为这些基本回文串一定分属于两个不同的大回文串。然后用 HashHash 判重复即可。
不过有唯一的特例，aaaa 包含了 aaa，这很好解决。对于位置 ii，其上的字符为 XX,先匹配长度为 33 的奇回文，如果匹配成功，那一定是 SXSSXS 的形式，紧接着，如果长度为 44 的偶回文匹配成功，那一定是 SXSYSXSY 的形式，因为是偶回文，所以四个字母都必须相等，显然不满足。故匹配成功直接 continuecontinue 即可。

代码

//  Created by Sengxian on 11/29/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 257
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int maxl = 255 + 3, hashBase = 1007;
char str[maxl];
int n;

//只用考虑3位以及4位的回文即可
set<ull> palindromes;
inline bool isPalinword(const char *str) {
    n = strlen(str);
    palindromes.clear();
    for(int i = 1; i < n - 1; ++i) {
        ull hashNum = str[i - 1] * hashBase * hashBase + str[i] * hashBase + str[i + 1];
        if(str[i - 1] == str[i + 1]) {
            palindromes.insert(hashNum);
            if(palindromes.size() >= 2) return true;
            continue; //到这里一定是 SXS 的形式，如果偶回文成功，必然是 XXXX 才能成功，显然不满足条件 
        }
        if(i == n - 2) continue;
        if(str[i] == str[i + 1] && str[i - 1] == str[i + 2]) {
            hashNum = hashNum * hashBase + str[i + 2];
            palindromes.insert(hashNum);
        }
        if(palindromes.size() >= 2) return true; 
    }
    return false;
}

int main() {
    while(~scanf("%s", str))
        if(isPalinword(str))
                printf("%s\n", str);
    return 0;
}
网络流之 - 匹配、边覆盖、独立集、顶点覆盖