Cod sursa(job #192415)

Utilizator raduzerRadu Zernoveanu raduzer Data 31 mai 2008 11:28:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#include <string.h>

int n,m,k,i,j,t,a[2000005],b[2000005],q,c[1005];
char s[2000005];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(s,100002,stdin);
	k=strlen(s)-1;
	for (i=1; i<=k; ++i) b[i]=b[i-1]+(s[i-1]-'a');
	fgets(s,1010,stdin);
	n=strlen(s)-1;
	int sol=0;
	for (i=1; i<=n; ++i) a[i]=a[i-1]+(s[i-1]-'a');
	for (i=k; i<=n; ++i)
		if (b[k]==a[i]-a[i-k])
		{
			q=1;
			for (j=1; j<=k; ++j) if (b[j]!=a[i-k+j]-a[i-k]) { q=0; break; }
			if (q) ++sol;
			if (sol<=1000) c[sol]=i-k;
		}
	printf("%d\n",sol);
	for (i=1; i<=sol; ++i) printf("%d ",c[i]);
	return 0;
}