test/aoj/2444_2.test.cpp

View this file on GitHub
Last update: 2022-09-01 14:18:35+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444

Depends on

string/rolling_hash.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2444"

// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

#include "../../string/rolling_hash.hpp"

using namespace std;
using llong = long long;
using ull = unsigned long long;

llong n, m;
string s;
char com;
string op;
set<tuple<ull, ull>> st;

int main() {
    cin >> n >> m;
    cin >> s;

    MRollingHash<1710> rh(s);
    RollingHash<1709, 998244353> h(s);

    llong l, r;
    l = r = 0;

    for (int i = 0; i < m; i++) {
        cin >> com >> op;

        if (com == 'L') {
            if (op == "++")
                l++;
            else
                l--;
        } else if (com == 'R') {
            if (op == "++")
                r++;
            else
                r--;
        }

        st.insert(make_tuple(rh.get_hash(l, r + 1), h.get_hash(l, r + 1)));
    }

    cout << st.size() << endl;
};

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

// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>

#line 1 "string/rolling_hash.hpp"



#include <cstdint>

//===
//#include <cstdint>
template <uint64_t base, uint64_t mod>
struct RollingHash {
    const std::string s;
    const int len;
    std::vector<uint64_t> hashed, power;

    RollingHash(const std::string &s) : s(s), len(s.size()) {
        hashed.assign(len + 1, 0);
        power.assign(len + 1, 1);

        for (int i = 0; i < len; i++) {
            hashed[i + 1] = (hashed[i] * base + s[i]) % mod;
            power[i + 1] = power[i] * base % mod;
        }
    };

    // s[l, r)
    uint64_t get_hash(int l, int r) {
        uint64_t res = hashed[r] + mod - hashed[l] * power[r - l] % mod;
        if (res >= mod) res -= mod;
        return res;
    };
};

template <uint64_t base>
struct RollingHash<base, (1ull << 61ull) - 1ull> {
    const std::string s;
    const int len;
    const uint64_t mask30 = (1ull << 30ull) - 1ull;
    const uint64_t mask31 = (1ull << 31ull) - 1ull;
    const uint64_t mod = (1ull << 61ull) - 1ull;
    std::vector<uint64_t> hashed, power;

    RollingHash(const std::string &s) : s(s), len(s.size()) {
        hashed.assign(len + 1, 0);
        power.assign(len + 1, 1);

        for (int i = 0; i < len; i++) {
            hashed[i + 1] = calc_mod(mul(hashed[i], base) + s[i]);
            power[i + 1] = calc_mod(mul(power[i], base));
        }
    };

    // s[l, r)
    uint64_t get_hash(int l, int r) {
        uint64_t res = hashed[r] + mod - calc_mod(mul(hashed[l], power[r - l]));
        if (res >= mod) res -= mod;
        return res;
    };

    inline uint64_t mul(uint64_t l, uint64_t r) {
        uint64_t lu = l >> 31;
        uint64_t ld = l & mask31;
        uint64_t ru = r >> 31;
        uint64_t rd = r & mask31;
        uint64_t mid = ld * ru + lu * rd;

        return ((lu * ru) << 1) + (mid >> 30) + ((mid & mask30) << 31) +
               ld * rd;
    };

    inline uint64_t calc_mod(uint64_t v) {
        v = (v & mod) + (v >> 61);
        if (v >= mod) v -= mod;
        return v;
    };
};

template <uint64_t base>
using MRollingHash = RollingHash<base, (1ull << 61ull) - 1ull>;
//===


#line 20 "test/aoj/2444_2.test.cpp"

using namespace std;
using llong = long long;
using ull = unsigned long long;

llong n, m;
string s;
char com;
string op;
set<tuple<ull, ull>> st;

int main() {
    cin >> n >> m;
    cin >> s;

    MRollingHash<1710> rh(s);
    RollingHash<1709, 998244353> h(s);

    llong l, r;
    l = r = 0;

    for (int i = 0; i < m; i++) {
        cin >> com >> op;

        if (com == 'L') {
            if (op == "++")
                l++;
            else
                l--;
        } else if (com == 'R') {
            if (op == "++")
                r++;
            else
                r--;
        }

        st.insert(make_tuple(rh.get_hash(l, r + 1), h.get_hash(l, r + 1)));
    }

    cout << st.size() << endl;
};