Cod sursa(job #1019776)

Utilizator taigi100Cazacu Robert taigi100 Data 31 octombrie 2013 21:53:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
/*
          ~Keep It Simple!~
*/

#define MaxLenght 2000001

#include<stdio.h>
#include<string.h>

char Pattern[MaxLenght],Str[MaxLenght];
int BadMatchTable[256],MatchesNumber,Matches[MaxLenght];

void PreProcess_BadMatchTable()
{
	int PatternLenght = strlen ( Pattern );

	for ( int i = 0 ; i <= 256 ; i ++ )

		BadMatchTable[i] = PatternLenght;

	for ( int i = 0 ; i < PatternLenght - 1 ; i ++ )
	
		BadMatchTable[ Pattern [ i ] ] = PatternLenght - i - 1 ;
}

char* FindMatch(char* Pattern,char* SearchLocation)
{
	int PatternLenght = strlen ( Pattern ) ;
	int LocationLenght = strlen ( SearchLocation ) ;
	int i = PatternLenght - 1;
	int j = 0;

	while( j < ( LocationLenght - PatternLenght + 1 ) )
	{
		if ( SearchLocation [ i+j ] == Pattern [ i ] )
			i--;
		else
		{
			j += BadMatchTable[ SearchLocation [ i+j ] ];
			i = PatternLenght - 1;
		}
		if ( i == -1 )
			return SearchLocation + j;
	}

	return NULL;
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	scanf("%s %s",Pattern,Str);

	PreProcess_BadMatchTable();

	char* match = FindMatch(Pattern,Str);
    while ( match )
	{
		Matches [ ++MatchesNumber ] = match - Str;
		match = FindMatch(Pattern,match+1);
	}

	printf("%d\n",MatchesNumber);
	for(int i= 1; i<=MatchesNumber; i++)
		printf("%d ",Matches[i]);
    
}