Cod sursa(job #2868318)

Utilizator alextmAlexandru Toma alextm Data 10 martie 2022 21:01:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector<int> prefix(string &pattern, int n) {
	vector<int> pi(n + 1);
	for(int i = 2, q = 0; i <= n; i++) {
		while(q && pattern[q + 1] != pattern[i])
			q = pi[q];
		if(pattern[q + 1] == pattern[i])
			q++;
		pi[i] = q;
	}
	return pi;
}

vector<int> KMP(string text, string pattern) {
	int n = (int) text.length();
	int m = (int) pattern.length();
	text = '$' + text;
	pattern = '$' + pattern;
	
	vector<int> pi = prefix(pattern, m);
	vector<int> ans;
	
	for(int i = 1, q = 0; i <= n; i++) {
		while(q && pattern[q + 1] != text[i])
			q = pi[q];
		if(pattern[q + 1] == text[i])
			q++;
		if(q == m) {
			q = pi[q];
			if((int) ans.size() <= 1000)
				ans.push_back(i - m);
		}
	}
	return ans;
}

int main() {
	string A, B;
	fin >> A >> B;
	
	vector<int> ans = KMP(B, A);
	
	fout << (int) ans.size() << '\n';
	for(int id : ans)
		fout << id << ' ';
	fout << '\n';
	
	return 0;
}