Cod sursa(job #1019737)

Utilizator taigi100Cazacu Robert taigi100 Data 31 octombrie 2013 21:11:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
/*
          ~Keep It Simple!~
*/
#include<stdio.h>
#include<string.h>
char A[2000001],B[2000001];
int dictionary[200],nrs,v[100000];

void PreProcess_Dictionary()
{
	int len = strlen(A);
	for(int i=0;i<=200;i++)
		dictionary[i]=len;
	for(int i=0; i < len - 1; i++)
		dictionary[A[i]]=len-i - 1;
}

void Search_Pattern()
{
	int len = strlen(A) - 1,len2 = strlen(B);
	int i=len,j=0;
	while(j<(len2-len+1))
	{
		if(A[i] == B[i+j]) 
			i--;
		else if(A[i] != B[i+j]) 
		{
			j+=dictionary[B[i+j]];
			i=len;
		}
		if(i == -1) 
		{
			v[++nrs] = j;
			i = len;
			j += dictionary[B[j]];
		}
	}
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

    scanf("%s %s",A,B);	
	PreProcess_Dictionary();

    Search_Pattern();
	printf("%d\n",nrs);
	for(int i=1;i<=nrs;i++)
		printf("%d ",v[i]);
	return 0;
}