Cod sursa(job #463922)

Utilizator darrenRares Buhai darren Data 17 iunie 2010 22:48:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;

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

void make_prefix()
{
	int k = -1;
	prefix[0] = -1;
	for (int i = 1; i < strlen(a); ++i)
	{
		while (k != -1 && a[k + 1] != a[i])
			k = prefix[k];
		if (a[k + 1] == a[i])
			++k;
		prefix[i] = k;
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	fgets(a, sizeof(a), stdin);
	fgets(b, sizeof(b), stdin);
	a[strlen(a) - 1] = '\0';
	b[strlen(b) - 1] = '\0';
	
	make_prefix();
	
	int ok = -1;
	for (int i = 0; i < strlen(b); ++i)
	{
		
		while (ok != -1 && a[ok + 1] != b[i])
			ok = prefix[ok];
		
		if (a[ok + 1] == b[i])
			++ok;
		
		if (ok == strlen(a) - 1)
		{
			++n;
			if (n <= 1000)
				pos[n] = i - strlen(a) + 1;
		}
	}
	printf("%d \n", n);
	for (int i = 1; i <= min(n, 1000); ++i)
		printf("%d ", pos[i]);
}