library/test/aoj/2444-Substring.hash.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2444

Depends on

• library/string/rollingHash.hpp

Code

#include <bits/stdc++.h>
using namespace std;
#include "../../string/rollingHash.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2444"
#define ll long long

int main() {
    ios_base::sync_with_stdio(0);
    string str, s;
    int n, q;
    cin>>n>>q; cin.ignore();
    getline(cin, str);

    RollingHash rh(str);
    set<pair<ll, ll>> st;
    int l=0, r=0;
    while(q--) {
        cin>>s;
        if(s=="L++") {
            l++;
        } else if(s=="L--") {
            l--;
        } else if(s=="R++") {
            r++;
        } else {
            r--;
        }
        assert(l>=0 && r>=0);
        st.insert({rh.get(l, r+1, 0), rh.get(l, r+1, 1)});
    }    
    cout<<st.size()<<'\n';
    return 0;
}

#line 1 "library/test/aoj/2444-Substring.hash.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "library/string/rollingHash.hpp"

struct RollingHash {
    static constexpr int M = 2;
    static constexpr long long MODS[M] = {999999937, 1000000007};
    static constexpr long long BASE = 9973;
    vector<long long> powb[M], hash[M];
    int n;
    RollingHash() {}
    RollingHash(const string& str) { init(str); }
    void init(const string& str) {
        n = str.size();
        for (int k = 0; k < M; k++) {
            powb[k].resize(n + 1, 1);
            hash[k].resize(n + 1, 0);
            for (int i = 0; i < n; i++) {
                hash[k][i + 1] = (hash[k][i] * BASE + str[i]) % MODS[k];
                powb[k][i + 1] = powb[k][i] * BASE % MODS[k];
            }
        }
    }
    // get hash str[l,r)
    long long get(int l, int r, int k) {
        long long res = hash[k][r] - hash[k][l] * powb[k][r - l] % MODS[k];
        if (res < 0) res += MODS[k];
        return res;
    }
};

bool match(RollingHash& rh1, int l1, int r1, RollingHash& rh2, int l2, int r2) {
    bool res = true;
    for (int k = 0; k < RollingHash::M; k++) {
        res &= rh1.get(l1, r1, k) == rh2.get(l2, r2, k);
    }
    return res;
}
#line 4 "library/test/aoj/2444-Substring.hash.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2444"
#define ll long long

int main() {
    ios_base::sync_with_stdio(0);
    string str, s;
    int n, q;
    cin>>n>>q; cin.ignore();
    getline(cin, str);

    RollingHash rh(str);
    set<pair<ll, ll>> st;
    int l=0, r=0;
    while(q--) {
        cin>>s;
        if(s=="L++") {
            l++;
        } else if(s=="L--") {
            l--;
        } else if(s=="R++") {
            r++;
        } else {
            r--;
        }
        assert(l>=0 && r>=0);
        st.insert({rh.get(l, r+1, 0), rh.get(l, r+1, 1)});
    }    
    cout<<st.size()<<'\n';
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	28 ms	7 MB
g++	testcase_01	AC	34 ms	8 MB
g++	testcase_02	AC	133 ms	32 MB
g++	testcase_03	AC	129 ms	27 MB
g++	testcase_04	AC	116 ms	19 MB
g++	testcase_05	AC	82 ms	18 MB
g++	testcase_06	AC	61 ms	16 MB
g++	testcase_07	AC	64 ms	16 MB
g++	testcase_08	AC	58 ms	15 MB
g++	testcase_09	AC	64 ms	16 MB
g++	testcase_10	AC	64 ms	17 MB
g++	testcase_11	AC	65 ms	16 MB
g++	testcase_12	AC	66 ms	17 MB
g++	testcase_13	AC	64 ms	16 MB
g++	testcase_14	AC	70 ms	15 MB
g++	testcase_15	AC	69 ms	15 MB
g++	testcase_16	AC	68 ms	15 MB
g++	testcase_17	AC	68 ms	15 MB
g++	testcase_18	AC	68 ms	15 MB
g++	testcase_19	AC	6 ms	4 MB
g++	testcase_20	AC	5 ms	4 MB
g++	testcase_21	AC	5 ms	4 MB
g++	testcase_22	AC	5 ms	4 MB
g++	testcase_23	AC	5 ms	4 MB
g++	testcase_24	AC	5 ms	4 MB
g++	testcase_25	AC	5 ms	4 MB

Back to top page