Cod sursa(job #1006332)

Utilizator andreiiiiPopa Andrei andreiiii Data 6 octombrie 2013 21:09:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000002
using namespace std;

char a[N], b[N];
int pi[N], sol[1001];

void kmp()
{
	int q=0, i;
	for(i=2;a[i]!='\n'&&a[i]!='\0';i++)
	{
		while(q&&a[q+1]!=a[i]) q=pi[q];
		if(a[q+1]==a[i]) q++;
		pi[i]=q;
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	int i, q=0, soll=0, m;
	a[0]='0';
	gets(a+1);
	m=strlen(a)-1;
	gets(b+1);
	kmp();
	for(i=1;b[i]!='\n'&&b[i]!='\0';i++)
	{
		while(q&&a[q+1]!=b[i]) q=pi[q];
		if(a[q+1]==b[i]) q++;
		if(q==m)
		{
			soll++;
			if(soll<=1000) sol[soll]=i-m;
		}
	}
	printf("%d\n", soll);
	for(i=1;i<=min(soll, 1000);i++) printf("%d ", sol[i]);
}