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;
}