test/ALDS1_14_B.test.cpp

• View this file on GitHub
• Last update: 2025-05-28 17:58:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B

Depends on

• Segment Tree (data_structure/segment_tree.hpp)
• string/rolling_hash.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B"

#include <data_structure/segment_tree.hpp>  // for SegmentTree
#include <fastio/base.hpp>                  // for FASTIO, cin, cout
#include <fastio/signed/write.hpp>          // for operator<<
#include <fastio/string/read.hpp>           // for operator>>
#include <fastio/string/write.hpp>          // for operator<<
#include <fastio/vector/write.hpp>          // for operator<<
#include <string/rolling_hash.hpp>          // for RollingHash
#include <string>                           // for basic_string, string
#include <templates/macro/abbrev/endl.hpp>  // for endl
#include <templates/macro/segtree/RSQ.hpp>  // for RSQ
#include <templates/rep.hpp>                // for rep
#include <templates/template.hpp>
#include <templates/vector_output.hpp>  // for operator+
#include <vector>                       // for vector

using namespace std;

int main() {
    string t, s;
    cin >> t >> s;
    using rh = RollingHash;
    vector<rh> v;
    rep(i, (int)t.size()) {
        v.emplace_back(rh{t[i]});
    }
    SegmentTree<RSQ(rh, rh{})> seg(v);
    vector<int> ans;
    rh c = rh{s};
    rep(l, (int)t.size()) {
        int r = l + (int)s.size() - 1;
        if ((int)t.size() <= r) break;
        if (seg(l, r + 1) == c) {
            ans.emplace_back(l);
        }
    }
    cout << (ans + endl);
}

#line 1 "test/ALDS1_14_B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B"

#include <data_structure/segment_tree.hpp>  // for SegmentTree
#include <fastio/base.hpp>                  // for FASTIO, cin, cout
#include <fastio/signed/write.hpp>          // for operator<<
#include <fastio/string/read.hpp>           // for operator>>
#include <fastio/string/write.hpp>          // for operator<<
#include <fastio/vector/write.hpp>          // for operator<<
#include <string/rolling_hash.hpp>          // for RollingHash
#include <string>                           // for basic_string, string
#include <templates/macro/abbrev/endl.hpp>  // for endl
#include <templates/macro/segtree/RSQ.hpp>  // for RSQ
#include <templates/rep.hpp>                // for rep
#include <templates/template.hpp>
#include <templates/vector_output.hpp>  // for operator+
#include <vector>                       // for vector

using namespace std;

int main() {
    string t, s;
    cin >> t >> s;
    using rh = RollingHash;
    vector<rh> v;
    rep(i, (int)t.size()) {
        v.emplace_back(rh{t[i]});
    }
    SegmentTree<RSQ(rh, rh{})> seg(v);
    vector<int> ans;
    rh c = rh{s};
    rep(l, (int)t.size()) {
        int r = l + (int)s.size() - 1;
        if ((int)t.size() <= r) break;
        if (seg(l, r + 1) == c) {
            ans.emplace_back(l);
        }
    }
    cout << (ans + endl);
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	32 ms	4 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	01_small_02.in	AC	4 ms	4 MB
g++	01_small_03.in	AC	4 ms	4 MB
g++	02_rand_00.in	AC	4 ms	4 MB
g++	02_rand_01.in	AC	4 ms	4 MB
g++	02_rand_02.in	AC	4 ms	4 MB
g++	02_rand_03.in	AC	4 ms	4 MB
g++	02_rand_04.in	AC	5 ms	4 MB
g++	02_rand_05.in	AC	6 ms	4 MB
g++	02_rand_06.in	AC	7 ms	5 MB
g++	02_rand_07.in	AC	22 ms	20 MB
g++	03_large_00.in	AC	7 ms	5 MB
g++	03_large_01.in	AC	7 ms	5 MB
g++	03_large_02.in	AC	22 ms	20 MB
g++	03_large_03.in	AC	23 ms	20 MB
g++	03_large_04.in	AC	154 ms	140 MB
g++	03_large_05.in	AC	158 ms	140 MB
g++	03_large_06.in	AC	295 ms	138 MB
g++	03_large_07.in	AC	294 ms	138 MB
g++	03_large_08.in	AC	294 ms	138 MB
g++	03_large_09.in	AC	296 ms	138 MB
g++	04_embedded_00.in	AC	246 ms	141 MB
g++	04_embedded_01.in	AC	245 ms	140 MB
g++	04_embedded_02.in	AC	294 ms	138 MB
g++	04_embedded_03.in	AC	295 ms	139 MB
g++	04_embedded_04.in	AC	295 ms	138 MB
g++	04_embedded_05.in	AC	295 ms	138 MB
g++	05_corner_00.in	AC	5 ms	4 MB
g++	05_corner_01.in	AC	4 ms	4 MB
g++	05_corner_02.in	AC	4 ms	4 MB
g++	05_corner_03.in	AC	264 ms	150 MB
g++	05_corner_04.in	AC	316 ms	153 MB
g++	05_corner_05.in	AC	293 ms	138 MB
g++	05_corner_06.in	AC	293 ms	138 MB

Back to top page