Cod sursa(job #383603)

Utilizator avram_florinavram florin constantin avram_florin Data 17 ianuarie 2010 11:17:34
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define M 2000010

using namespace std;

int n,m,nr,urm[M],v[1001];
char s[M],p[M],aux[M];

void prefix()
{
	int q,k;
	q=2;
	urm[1]=0;
	k=0;
	for(q=2;q<=m;q++)
		{
			while(k>0&&p[k+1]!=p[q])
				k=urm[k];
			if(p[k+1]==p[q])
				k++;
			urm[q]=k;
		}
}

void solve()
{
	int i,q;
	q=m+1;
	for(i=1;i<=n;i++)
		{
			while(q>0&&p[q+1]!=s[i])
				q=urm[q];
			if(s[i]==p[q+1])
				q++;
			if(q==m)
				{
					nr++;
					if(nr<=1000)
						v[nr]=i-m;
						else
						break;
				}
		}
}

void print()
{
	int i ;
	printf("%d\n" , nr);
	for(i=1;i<nr;i++)
		printf("%d " , v[i]);
	printf("%d\n" , v[nr]);
}
 
int main ()
{
	freopen("strmatch.in" , "r" , stdin);
	freopen("strmatch.out" , "w" , stdout);
	scanf("%s" , &aux);
	p[0]=' ';
	strcat(p,aux);
	m=strlen(p)-1;
	s[0]=' ';
	scanf("%s" , &aux);
	strcat(s,aux);
	n=strlen(s)-1;
	prefix();
	solve();
	print();
	return 0;
}