Cod sursa(job #172025)

Utilizator a7893Nae Mihai a7893 Data 5 aprilie 2008 17:11:51
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#include<string.h>
#define N 20000
char a[N],b[N];
int n,m,pi[N],nr,poz[N];
void prefix()
{
	int i,k;
	pi[1]=0;
	k=0;
	for(i=2;i<=n;i++)
	{
		while(k>0&&a[k+1]!=a[i])
			k=pi[k];
		if(a[k+1]==a[k])
			k++;
		pi[i]=k;
	}
}
void kmp()
{
	int i,q;
	q=0;
	for(i=1;i<=m;i++)
	{
		while(q>0&&a[q+1]!=b[i])
			q=pi[q];
		if(a[q+1]==b[i])
			q++;
		if(q==n)
			poz[++nr]=i-n;
	}
}
void afis()
{
	int i;
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
		printf("%d ",poz[i]);
}


void solve()
{
	scanf("%s\n",&a);
	n=strlen(a);
	for(int i=n;i>=1;i--)
		a[i]=a[i-1];
	scanf("%s",&b);
	m=strlen(b);
	for(int i=m;i>=1;i--)
   	b[i]=b[i-1];
	prefix();
	kmp();
	afis();
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	solve();
	return 0;
}