Cod sursa(job #1019797)

Utilizator taigi100Cazacu Robert taigi100 Data 31 octombrie 2013 22:25:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
/*
          ~Keep It Simple!~
*/

#define MaxLenght 2000001

#include<stdio.h>
#include<string.h>
#include<stdlib.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 ++ )
	{
		int aux = Pattern[i];
		BadMatchTable[ aux ] = PatternLenght - i - 1 ;
	}
}

char* FindMatch(char* Pattern,char* SearchLocation)
{
	int PatternLenght = strlen ( Pattern ) ;
	int LocationLenght = strlen ( SearchLocation ) ;


	while( LocationLenght >= PatternLenght )
	{
		for( int i = PatternLenght - 1; SearchLocation[i] == Pattern[i]; i-- )
			if ( i == 0 )
				return SearchLocation;
		int aux = SearchLocation[PatternLenght - 1]; 
		LocationLenght -= BadMatchTable[aux];
		SearchLocation += BadMatchTable[aux];
	}

	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]);
    
	fclose(stdout);
	fclose(stdin);
}