困难的回文串(哈希模板)
程序员文章站
2024-03-16 22:43:28
...
Description
是的没错,学chang就是这么的菜,WA了34次才把这道题过了。题目很简单,就是让你判断一个字符串是否为回文串。仅此而已。
Input
测试数据有多组:
对于每组测试数据输入一个n表示字符串长度,接着输入长度为n的字符串(1 <= n <= 1e7)
Output
对于每组输出判断当前字符串是否为回文串,如果是回文串输出YES,否则输出NO。
Sample Input Copy
6
aaaaaa
6
xuejie
Sample Output Copy
YES
NO
#include<bits/stdc++.h>
using namespace std;
const int mod=1e5;
const int n=131;
char s;
unsigned long long hs1,hs2;
int len;
int x;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
while(cin>>len)
{
hs1 = 0;
hs2 = 0;
x=1;
if(len == 1)
{
cin>>s;
cout<<"YES"<<endl;
continue;
}
for(int i=1; i<=len/2; i++)//正着算
{
cin>>s;
hs1 = (hs1*n+s)%mod;
}
if(len & 1)
{
cin>>s;
}
for(int i=1; i<=len/2; i++)//倒着算
{
cin>>s;
hs2 = (s*x+hs2)%mod;
x = x*n%mod;
}
// cout<<hs1<<' '<<hs2<<endl;
if(hs1==hs2) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
上一篇: JAVA(文件)输入输出流
下一篇: set(洛谷)P4305不重复数字