test/string/kmp/aoj-alds1-String-Search.test.cpp

View this file on GitHub
Last update: 2023-07-20 17:15:06+08:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

library/string/kmp.hpp

Code

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

#include <iostream>
#include <cstring>
#include <vector>
#include "../../../library/string/kmp.hpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s, t;
	cin >> s >> t;
	int n = (int) s.size(), m = (int) t.size();
	string z = t + "#" + s;
	auto f = KMP(z);
	for(int i = m; i < n + m + 1; i++) {
		if(f[i] == m) {
			cout << i - 2 * m << "\n";
		}
	}
	return 0;
}

#line 1 "test/string/kmp/aoj-alds1-String-Search.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"

#include <iostream>
#include <cstring>
#include <vector>
#line 4 "library/string/kmp.hpp"
#include <algorithm>

#include <numeric>


namespace felix {

template<class T>
std::vector<int> KMP(const std::vector<T>& a) {
	int n = a.size();
	std::vector<int> k(n);
	for(int i = 1; i < n; ++i) {
		int j = k[i - 1];
		while(j > 0 && a[i] != a[j]) {
			j = k[j - 1];
		}
		j += (a[i] == a[j]);
		k[i] = j;
	}
	return k;
}

std::vector<int> KMP(const std::string& s) {
	return KMP(std::vector<int>(s.begin(), s.end()));
}

} // namespace felix

#line 7 "test/string/kmp/aoj-alds1-String-Search.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s, t;
	cin >> s >> t;
	int n = (int) s.size(), m = (int) t.size();
	string z = t + "#" + s;
	auto f = KMP(z);
	for(int i = m; i < n + m + 1; i++) {
		if(f[i] == m) {
			cout << i - 2 * m << "\n";
		}
	}
	return 0;
}