Cod sursa(job #2066799)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 15 noiembrie 2017 15:37:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;

#define MAXLEN 2000003

char s[MAXLEN], p[MAXLEN];
int pref[MAXLEN];
int n, m;

void buildPref() {
	int i = 0, j = -1;
	pref[0] = -1;

	while (i < m) {
		while (j >= 0 && p[i] != p[j])
			j = pref[j];

		i++, j++;
		pref[i] = j;
	}
}

vector<int> strMatch() {
	vector<int> sol;

	int i = 0, j = 0;

	while (i < n) {
		while (j >= 0 && s[i] != p[j])
			j = pref[j];

		i++, j++;

		if (j == m) {
			j = pref[j];
			sol.push_back(i - m);
		}
	}

	return sol;
}

void read() {
	scanf("%s %s ", p, s);
	n = strlen(s);
	m = strlen(p);
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	read();
	buildPref();
	auto result = strMatch();

	printf("%d\n", result.size());
	for(int item: result)
		printf("%d ", item);

	return 0;
}