test/knuth_morris_pratt.aoj.ALDS1_14_B.test.cpp

View this file on GitHub
Last update: 2020-05-16 01:16:19+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

lib/knuth_morris_pratt.hpp

Code

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

#include <iostream>
#include <string>
#include "../lib/knuth_morris_pratt.hpp"

int main(){
    std::string s, t; std::cin >> s >> t;
    auto ans = kmp(s, t);
    for (int i : ans) std::cout << i << std::endl;
    return 0;
}

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

#include <iostream>
#include <string>
#line 1 "lib/knuth_morris_pratt.hpp"



#include <vector>
#line 6 "lib/knuth_morris_pratt.hpp"

// Find a string t from a string s.
// For each element i in returned vector,
// s.substr(i, t.size()) == t holds.
// Assume '#' is not in s and t.
// Actually, this is the Morris-Pratt algorithm.
std::vector<int> kmp(const std::string &s, std::string t) {
    int n = s.size(), m = t.size();
    std::vector<int> id(m + 1);
    id[0] = -1;
    int j = -1;
    for (int i = 0; i < m; i++) {
        while (j >= 0 && t[i] != t[j]) j = id[j];
        id[i + 1] = ++j;
    }
    t += '#';
    std::vector<int> ret;
    int is = 0, it = 0;
    while (is < n) {
        if (s[is] == t[it]) is++, it++;
        else if (it == 0) is++;
        else it = id[it];
        if (it == m) {
            ret.push_back(is - m);
        }
    }
    return ret;
}


#line 6 "test/knuth_morris_pratt.aoj.ALDS1_14_B.test.cpp"

int main(){
    std::string s, t; std::cin >> s >> t;
    auto ans = kmp(s, t);
    for (int i : ans) std::cout << i << std::endl;
    return 0;
}