Submission #533061

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

#define REP(i, n) for (int i=0;i<int(n);++i)
#define ALL(A) (A).begin(),(A).end()
#define SZ(A) int(A.size())
#define PB push_back

using namespace std;

typedef unsigned long long ull;

struct RollingHash{
  static const ull p=100000007;
  string s;
  int n;
  vector<ull> pow, ph;
  
  RollingHash(string s) : s(s), n(SZ(s)), pow(n+1), ph(n+1){
    pow[0]=1,ph[0]=0;
    REP(i, n)ph[i+1]=s[i]+ph[i]*p,pow[i+1]=pow[i]*p;
  }
  
  static ull hash(const string &t) {
    ull h=0;
    REP(i,SZ(t))h=t[i]+h*p;
    return h;
  }  

  inline ull hash(int b, int e){
    return ph[e]-ph[b]*pow[e-b];
  }
  
  inline int find(string t) {
    int w=t.size(),count=0;
    if(w > SZ(s))return 0;
    ull h=hash(t);
    REP(i,n-w+1)count+=(hash(i,i+w)==h);
    return count;
  }

  int find(string t1,string t2){
    int count=0;
    if(5>SZ(s))return 0;
    ull h1=hash(t1),h2=hash(t2);
    REP(i,n-4){
      if(hash(i,i+5)==h1 || hash(i,i+5)==h2)count++,i+=4;
    }
    return count;
  }
};

int main(void){

  int n;
  cin >> n;
  string s;
  while(n--){
    cin >> s;
    cout << RollingHash(s).find("tokyo","kyoto") << endl;
  }
  return 0;
}

Submission Info

Judge Result