Cod sursa(job #1018501)

Utilizator taigi100Cazacu Robert taigi100 Data 29 octombrie 2013 18:02:30
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 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='a'; i<='z';i++)
		dictionary[i] = len-1;
	for(int i='A'; i<='Z'; i++)
		dictionary[i] = len-1;
	for(int i=0; i < len; 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-i))
	{
		if(A[i] == B[i+j]) 
			i--;
		else if(A[i] != B[i+j]) 
			i=len,j+=dictionary[B[i+j]];
		if(i == -1) 
		{
			v[++nrs] = j;
			i = len;
			j += len;
		}
	}
}
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;
}