test/aoj/2444.test.cpp

View this file on GitHub
Last update: 2020-10-27 19:04:41+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444

Depends on

string/rollinghash.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../string/rollinghash.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  string s;
  cin>>s;
  const int MOD = 1e9+7;
  const int B1 = 1e8+7;
  const int B2 = 1777771;
  RollingHash<int, MOD, B1> rh1(s);
  RollingHash<int, MOD, B2> rh2(s);

  int l=0,r=1;
  set<pair<int, int>> sp;
  for(int i=0;i<m;i++){
    string t;
    cin>>t;
    if(t=="L++") l++;
    if(t=="L--") l--;
    if(t=="R++") r++;
    if(t=="R--") r--;
    sp.emplace(rh1.find(l,r),rh2.find(l,r));
  }

  cout<<sp.size()<<endl;
  return 0;
}

#line 1 "test/aoj/2444.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "string/rollinghash.cpp"

#line 3 "string/rollinghash.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T,T MOD,T B>
struct RollingHash{
  using ll = long long;
  vector<T> hash,po;
  RollingHash(vector<T> vs){init(vs);}
  RollingHash(string &s){
    vector<T> vs;
    for(char c:s) vs.emplace_back(c);
    init(vs);
  }
  void init(vector<T> vs){
    int n=vs.size();
    hash.assign(n+1,0);
    po.assign(n+1,1);
    for(int i=0;i<n;i++){
      hash[i+1]=((ll)hash[i]*B+vs[i])%MOD;
      po[i+1]=(ll)po[i]*B%MOD;
    }
  }
  //S[l, r)
  T find(int l,int r){
    T res=(ll)hash[r]+MOD-(ll)hash[l]*po[r-l]%MOD;
    return res>=MOD?res-MOD:res;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/2444.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  string s;
  cin>>s;
  const int MOD = 1e9+7;
  const int B1 = 1e8+7;
  const int B2 = 1777771;
  RollingHash<int, MOD, B1> rh1(s);
  RollingHash<int, MOD, B2> rh2(s);

  int l=0,r=1;
  set<pair<int, int>> sp;
  for(int i=0;i<m;i++){
    string t;
    cin>>t;
    if(t=="L++") l++;
    if(t=="L--") l--;
    if(t=="R++") r++;
    if(t=="R--") r--;
    sp.emplace(rh1.find(l,r),rh2.find(l,r));
  }

  cout<<sp.size()<<endl;
  return 0;
}