Cod sursa(job #1162288)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 31 martie 2014 19:05:58
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NMAX = 2000005;
int N,M,i,q,pi[NMAX],S[1005],sol;
char A[NMAX],B[NMAX];
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",A+1); N=strlen(A+1);
	scanf("%s",B+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(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)
	    {
	        sol++;
	        if(sol<=1000) S[sol]=i-N;
	    }
	}
	printf("%d\n",sol);
	for(i=1;i<=min(sol,1000);i++) printf("%d ",S[i]);
	return 0;
}