test/aoj_alds1_14_b.test.cpp

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B

Depends on

• KMP法 (string/kmp.cpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

#include "../string/kmp.cpp"

int main() {
    string text, pattern;
    cin >> text >> pattern;
    auto res = kmp_search(text, pattern);
    for (auto &&i : res) {
        cout << i << "\n";
    }
    return 0;
}

#line 1 "test/aoj_alds1_14_b.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

#line 1 "string/kmp.cpp"
vector<int> kmp_table(const string &s){
    int n = s.size();
    vector<int> table(n + 1);
    table[0] = -1;
    for (int i = 0, j = -1; i < n;) {
        while(j >= 0 && s[i] != s[j]) j = table[j];
        i++, j++;
        table[i] = j;
    }
    return table;
}

vector<int> kmp_search(const string &text, const string &pattern){
    int n = text.size(), m = pattern.size();
    vector<int> res;
    if(pattern.empty()){
        res.resize(n + 1);
        iota(res.begin(), res.end(), 0);
        return res;
    }
    auto table = kmp_table(pattern);
    for (int i = 0, j = 0; i < n;) {
        while(j >= 0 && text[i] != pattern[j]) j = table[j];
        i++, j++;
        if(j == m){
            res.emplace_back(i - j);
            j = table[j];
        }
    }
    return res;
}

/**
 * @brief KMP法
 */
#line 21 "test/aoj_alds1_14_b.test.cpp"

int main() {
    string text, pattern;
    cin >> text >> pattern;
    auto res = kmp_search(text, pattern);
    for (auto &&i : res) {
        cout << i << "\n";
    }
    return 0;
}

Back to top page