P6312 [PA2018] Palindrom

· · 题解

因为内存很小，所以不能开数组；因为字符串长度未给出，所以要一个一个读入字符。

判断一个字符串是否回文，相当于判断这个字符串从前往后与从后往前是否相等。故考虑进行字符串哈希。

Hash_s=s_1\times b^1+s_1\times b^2+s_2\times b^2+\cdots +s_{len}\times b^{len}

其中 b 是自选的一个质数，同时还应自选一个大于 b 的质数 mod。

Code

#include<cstdio>
const int b=1000037,mod=1000039;
int n;
long long x,y,f=1;
char c;
int main(){
    for(;(c=getchar())<'a';);
    for(;c>='a';c=getchar()){
        (f*=b)%=mod;
        (x+=f*(c-'a'))%=mod;
        ((y+=(c-'a'))*=b)%=mod;
    }
    puts(x==y?"TAK":"NIE");
    return 0;
}

注意：b 和 mod 取得过小可能会增加错误的概率。