library/test/aoj/ALDS1_14_B-String_Search.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/ALDS1_14_B

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/ALDS1_14_B"

int main() {
    ios_base::sync_with_stdio(0);
    string s, t;
    cin>>s>>t;  
    int n = s.size(), m = t.size();
    RollingHash hs(s), ht(t);
    for(int i=0;i<n-m+1;++i) {
        if(match(hs, i, i+m, ht, 0, m)) {
            cout<<i<<'\n';
        }
    }
    return 0;
}

#line 1 "library/test/aoj/ALDS1_14_B-String_Search.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/ALDS1_14_B-String_Search.hash.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"

int main() {
    ios_base::sync_with_stdio(0);
    string s, t;
    cin>>s>>t;  
    int n = s.size(), m = t.size();
    RollingHash hs(s), ht(t);
    for(int i=0;i<n-m+1;++i) {
        if(match(hs, i, i+m, ht, 0, m)) {
            cout<<i<<'\n';
        }
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	4 MB
g++	01_small_00.in	AC	6 ms	4 MB
g++	01_small_01.in	AC	6 ms	4 MB
g++	01_small_02.in	AC	6 ms	4 MB
g++	01_small_03.in	AC	6 ms	4 MB
g++	02_rand_00.in	AC	6 ms	4 MB
g++	02_rand_01.in	AC	6 ms	4 MB
g++	02_rand_02.in	AC	6 ms	4 MB
g++	02_rand_03.in	AC	6 ms	4 MB
g++	02_rand_04.in	AC	6 ms	4 MB
g++	02_rand_05.in	AC	6 ms	4 MB
g++	02_rand_06.in	AC	6 ms	4 MB
g++	02_rand_07.in	AC	9 ms	7 MB
g++	03_large_00.in	AC	6 ms	4 MB
g++	03_large_01.in	AC	6 ms	4 MB
g++	03_large_02.in	AC	10 ms	7 MB
g++	03_large_03.in	AC	10 ms	7 MB
g++	03_large_04.in	AC	43 ms	36 MB
g++	03_large_05.in	AC	45 ms	36 MB
g++	03_large_06.in	AC	37 ms	36 MB
g++	03_large_07.in	AC	37 ms	36 MB
g++	03_large_08.in	AC	35 ms	36 MB
g++	03_large_09.in	AC	37 ms	36 MB
g++	04_embedded_00.in	AC	37 ms	36 MB
g++	04_embedded_01.in	AC	36 ms	36 MB
g++	04_embedded_02.in	AC	38 ms	36 MB
g++	04_embedded_03.in	AC	37 ms	36 MB
g++	04_embedded_04.in	AC	37 ms	36 MB
g++	04_embedded_05.in	AC	37 ms	36 MB
g++	05_corner_00.in	AC	7 ms	4 MB
g++	05_corner_01.in	AC	5 ms	4 MB
g++	05_corner_02.in	AC	5 ms	4 MB
g++	05_corner_03.in	AC	88 ms	36 MB
g++	05_corner_04.in	AC	84 ms	36 MB
g++	05_corner_05.in	AC	39 ms	36 MB
g++	05_corner_06.in	AC	38 ms	36 MB

Back to top page