Cod sursa(job #163056)

Utilizator wefgefAndrei Grigorean wefgef Data 21 martie 2008 11:22:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define pb push_back
#define sz(c) int((c).size())

#define MAXN 2000005

int N, M;
char A[MAXN], B[MAXN];
int Pref[MAXN];
vector<int> ret;

inline int min(int a, int b) { return (a < b ? a : b); }

void Prefix() {
	int p = 0;
	Pref[1] = 0;
	for (int i = 2; i <= N; ++i) {
		while (p && A[p+1] != A[i])
			p = Pref[p];
		if (A[p+1] == A[i])
			++p;
		Pref[i] = p;
	}
}

void Matches() {
	int p = 0;
	for (int i = 1; i <= M; ++i) {
		while (p && B[i] != A[p+1])
			p = Pref[p];
		if (A[p+1] == B[i])
			++p;
		if (p == N) {
			ret.pb(i-N);
			p = Pref[p];
		}
	}
}

void ReadData() {
	scanf("%s", A+1);
	scanf("%s", B+1);
	N = strlen(A+1);
	M = strlen(B+1);
}

void WriteData() {
	printf("%d\n", sz(ret));
	for (int i = 0; i < min(sz(ret), 1000); ++i)
		printf("%d ", ret[i]);
}

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

	ReadData();
	Prefix();
	Matches();
	WriteData();
}