UVA 257 Palinwords（hash）題解

思路：給你字元串，如果他包含至少兩個長度大于等于3的回文，并且這些回文不能嵌套（例如aaa嵌套在aaaa，waw嵌套在awawa），如果這個字元串這麼牛逼的話，就輸出他。

思路：拿到字元串先正序hash和逆序hash，用來判斷回文串。這裡其實隻要判斷長度為3和4的回文就行，因為3，4大的可以嵌套在比他大的裡面。一開始我還在想怎麼區分aaa和aaaa，弄了個很複雜的東西，但是我發現其實隻要儲存回文串的半徑的hash就行了！這樣長度3和4也能比了。

代碼：

#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;
const int maxn = 255+10;
const int seed = 131;
const int MOD = 100013;
const int INF = 0x3f3f3f3f;
char s[maxn];
ull ha[2][maxn],bin[maxn];
void init(){
    bin[0] = 1;
    for(int i = 1; i <= 255; i++)
        bin[i] = bin[i - 1] * seed;
}
void HASH(int len){
    ha[0][0] = 0;
    for(int i = 1; i <= len; i++)   //順序
        ha[0][i] = ha[0][i - 1] * seed + s[i];
    ha[1][0] = 0;
    for(int i = len,j = 1; i >= 1; i--, j++)    //逆序
        ha[1][j] = ha[1][j - 1] * seed + s[i];
}
ull getsub(int l,int r,int id){
    return ha[id][r] - ha[id][l - 1] * bin[r - l + 1];
}
int main(){
    init();
    while(scanf("%s", s + 1) !=  EOF){
        int len = strlen(s + 1);
        HASH(len);
        int flag = -1;
        ull is;
        for(int i = 1; i <= len - 2; i++){
            ull suf = getsub(i, i + 1,0);   //順序
            ull pre = getsub(len - (i + 2) + 1, len - (i + 1) + 1, 1);   //逆序
            if(suf == pre){
                if(flag == -1){
                    is = suf;
                    flag = 0;
                }
                else if(suf != is){
                    flag = -2;
                    break;
                }
            }
        }
        if(flag == -2){
            printf("%s\n", s + 1);
            continue;
        }
        for(int i = 1; i<= len - 3; i++){
            ull suf = getsub(i, i + 1,0);   //順序
            ull pre = getsub(len - (i + 3) + 1, len - (i + 2) + 1, 1);   //逆序
            if(suf == pre){
                if(flag == -1){
                    is = suf;
                    flag = 0;
                }
                else if(suf != is){
                    flag = -2;
                    break;
                }
            }
        }
        if(flag == -2){
            printf("%s\n", s + 1);
            continue;
        }
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/KirinSB/p/9524642.html