Verify/knuth_morris_pratt.test.cpp

View this file on GitHub
Last update: 2020-08-28 20:17:14+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_14_B

Depends on

String/knuth_morris_pratt.hpp

Code

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

#include "../String/knuth_morris_pratt.hpp"

#include <iostream>
#include <string>

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::string s, p;
    std::cin >> s >> p;

    PatternMatching pm(p);
    for (auto i : pm.find(s)) std::cout << i << "\n";

    return 0;
}

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

#line 2 "String/knuth_morris_pratt.hpp"

#include <vector>

template <class Container>
struct PatternMatching {
    Container pat;
    std::vector<int> fail;

    explicit PatternMatching(const Container& pat) : pat(pat) {
        fail.resize(pat.size() + 1, -1);

        int fpos = -1;
        for (int pos = 0; pos < (int)pat.size(); ++pos) {
            if (fpos >= 0 && pat[pos] == pat[fpos]) fail[pos] = fail[fpos];

            while (fpos >= 0 && pat[pos] != pat[fpos]) {
                fpos = fail[fpos];
            }
            fail[pos + 1] = ++fpos;
        }
    }

    std::vector<int> find(const Container& s) {
        std::vector<int> ret;
        int pos = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            while (pos >= 0 && pat[pos] != s[i]) {
                pos = fail[pos];
            }
            if (++pos == (int)pat.size()) {
                ret.push_back(i - (int)pat.size() + 1);
                pos = fail[pos];
            }
        }
        return ret;
    }
};
#line 4 "Verify/knuth_morris_pratt.test.cpp"

#include <iostream>
#include <string>

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::string s, p;
    std::cin >> s >> p;

    PatternMatching pm(p);
    for (auto i : pm.find(s)) std::cout << i << "\n";

    return 0;
}