Cod sursa(job #1110929)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 18 februarie 2014 14:53:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int nmax = 2000005;
int n,m,i,j,pi[nmax],q,s[1005],cnt;
char a[nmax],b[nmax];
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",a+1); scanf("%s",b+1);
	n=strlen(a+1); m=strlen(b+1);
	for(i=2;i<=n;i++)
	{
	    while(q && a[i]!=a[q+1]) q=pi[q];
	    if(a[i]==a[q+1]) q++;
	    pi[i]=q;
	}
	for(q=0,i=1;i<=m;i++)
	{
	    while(q && b[i]!=a[q+1]) q=pi[q];
	    if(b[i]==a[q+1]) q++;
	    if(q==n && ++cnt<=1000) s[cnt]=i-n;
	}
	printf("%d\n",cnt);
	for(i=1;i<=min(cnt,1000);i++) printf("%d ",s[i]);
	return 0;
}