Cod sursa(job #2722030)

Utilizator raluca.rusuRaluca Maria Rusu raluca.rusu Data 12 martie 2021 16:01:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <string.h>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int maxn = 2000005;

char a[maxn], b[maxn];
int n, pi[maxn], m, k;
vector <int> matches;

int main() {

	cin >> a+1 >> b+1;
	n = strlen(a+1);
	m = strlen(b+1);

	k = 0;
	for(int i=2; i<=n; ++i) {
		while(k > 0 && a[k+1] != a[i])
			k = pi[k];
		if(a[k+1] == a[i])
			++k;
		pi[i] = k;
	}
	
	k = 0;
	for(int i=1; i<=m; ++i) {
		while(k > 0 && a[k+1] != b[i])
			k = pi[k];
		if(a[k+1] == b[i])
			++k;
		if(k == n)
			matches.push_back(i-n);
	}
	
	cout << matches.size() << '\n';
	for(int i=0; i < min(1000, int(matches.size())); ++i)
		cout << matches[i] << ' ';
}