Cod sursa(job #886307)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 22 februarie 2013 19:27:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>rez;
int p[200005];
char A[200005],B[200005];
int n,i,j,k,m,t;

void prefix()
{
	k=0;p[k]=0;
	for (i=2;i<=n;i++)
	{
		while (k && A[k+1]!=A[i]) k=p[k];
		if (A[k+1]==A[i]) k++;
		p[i]=k;
	}
}

void KMP()
{
	k=0;
	for (i=1;i<=m;i++)
	{
		while (k && A[k+1]!=B[i]) k=p[k];
		if (A[k+1]==B[i]) k++;
		if (k==n && rez.size()<1000) rez.push_back(i-n);
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(A+1);
	gets(B+1);
	n=strlen(A+1);
	m=strlen(B+1);
	prefix();
	KMP();
	printf("%d\n",rez.size());
	k=rez.size();
	for (i=0;i<k;i++) printf("%d ",rez[i]);
	return 0;
}