Cod sursa(job #486571)

Utilizator xdozeAnatole Duquele xdoze Data 21 septembrie 2010 23:34:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cctype>
#include <cstdio>
#include <algorithm>

char a[2000001], b[2000001];
int sa, sb, prefix[2000001];
int pos[1001], n;

void make_prefix()
{
	int q = 0;
	for (int i = 2; i <= sa; ++i)
	{
		while (q && a[i] != a[q + 1])
			q = prefix[q];
		if (a[i] == a[q + 1]) ++q;
		prefix[i] = q;
	}
}

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

	gets(a);
	gets(b);
	for (sa = 0; isdigit(a[sa]) || isalpha(a[sa]); ++sa);
	for (sb = 0; isdigit(b[sb]) || isalpha(b[sb]); ++sb);
	for (int i = sa; i > 0; --i) a[i] = a[i - 1];
	for (int i = sb; i > 0; --i) b[i] = b[i - 1];

	make_prefix();

	int q = 0;
	for (int i = 1; i <= sb; ++i)
	{
		while (q && a[q + 1] != b[i]) q = prefix[q];
		if (a[q + 1] == b[i]) ++q;
		if (q == sa)
		{
			q = prefix[q];
			if (n < 1000) pos[++n] = i - sa;
			else          ++n;
		}
	}

	printf("%d \n", n);
	for (int i = 1; i <= std::min(n, 1000); ++i)
		printf("%d ", pos[i]);
}