POJ3007 Organize Your Train part II
PCKの問題のはず。
普通に文字列のままやったらTLEして腹が立ったのでローリングハッシュ書いた。
結果、rank6位に。わーい。
http://poj.org/problemstatus?problem_id=3007
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pair<string,string>pss; typedef long long ll; ll mot=1000000007; string rev(string a) { reverse(a.begin(),a.end()); return a; } int main() { int data; scanf("%d",&data); for(int p=0;p<data;p++) { string str; cin>>str; ll hashl[72]; ll hashr[72]; ll rhashl[72]; ll rhashr[72]; ll now1=0,now2=0,now3=0,now4=0; ll kei=1; for(int i=0;i<str.size();i++) { now1*=mot; now4*=mot; now1+=str[i]; now4+=str[str.size()-1-i]; hashl[i]=now1; rhashr[str.size()-1-i]=now4; now2+=kei*str[str.size()-1-i]; now3+=kei*str[i]; hashr[str.size()-1-i]=now2; rhashl[i]=now3; kei*=mot; } vector<ll>vec; ll jou=1; for(int i=0;i<str.size()-1;i++) { jou*=mot; vec.push_back(hashr[i+1]*jou+hashl[i]); vec.push_back(hashr[i+1]*jou+rhashl[i]); vec.push_back(rhashr[i+1]*jou+hashl[i]); vec.push_back(rhashr[i+1]*jou+rhashl[i]); vec.push_back(hashl[str.size()-i-2]*jou+hashr[str.size()-i-1]); vec.push_back(hashl[str.size()-i-2]*jou+rhashr[str.size()-i-1]); vec.push_back(rhashl[str.size()-i-2]*jou+hashr[str.size()-i-1]); vec.push_back(rhashl[str.size()-i-2]*jou+rhashr[str.size()-i-1]); } sort(vec.begin(),vec.end()); ll now=-1; int ret=0; for(int i=0;i<vec.size();i++) { if(now!=vec[i]) { ret++; now=vec[i]; } } printf("%d\n",ret); } }