2217:Secretary
問題文
http://poj.org/problem?id=2217
蟻本で解説されてる問題。蟻本と週刊spaghetti sourceさんを参考にしてローリングハッシュで実装してみた。TLEになった。答えも正しく出てるのかはわからない。
#include<iostream> #include<algorithm> #include<string> #include<vector> #include<cstdio> #define all(c) (c).begin(),(c).end() using namespace std; typedef unsigned long long ull; ull B=100000007; ull rollihash(string s,int id,int m){ ull h=0; for(int i=id;i<min(id+m,(int)s.size());i++)h=s[i]+h*B; return h; } int main(void){ int n; string s,t; cin >> n; cin.ignore(); while(n--){ getline(cin,s); getline(cin,t); int sl=s.size(); s+="\0"+t; int tl=s.size(),ans=0; for(int i=0;i<sl;i++){ for(int j=sl+1;j<tl;j++){ int l=0,r=tl-j+1; while (r-l>1){ int m=(l+r)/2; if (rollihash(s,i,m)==rollihash(s,j,m))l=m; else r=m; } ans=max(ans,l); } } cout << "Nejdelsi spolecny retezec ma delku " << ans << "." << endl; } return 0; }