Cod sursa(job #1020386)

Utilizator taigi100Cazacu Robert taigi100 Data 2 noiembrie 2013 00:02:22
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 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[1001];
 
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 ;
    }
}
 
void 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 )
			{
			   if( MatchesNumber < 1000 )
               Matches [ ++MatchesNumber ] = SearchLocation - Str;
			}
        int aux = SearchLocation[PatternLenght - 1]; 
        LocationLenght -= BadMatchTable[aux];
        SearchLocation += BadMatchTable[aux];
    }
 
    return;
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
 
    scanf("%s %s",Pattern,Str);
    
	if( strlen(Pattern) > strlen(Str) )
	{
		printf("0");
		return 0;
	}

    PreProcess_BadMatchTable();
 
    FindMatch(Pattern,Str);

    printf("%d\n",MatchesNumber);
	int min = MatchesNumber > 1000 ? 1000:MatchesNumber;
    for(int i= 1; i<=min; i++)
        printf("%d ",Matches[i]);
     
    fclose(stdout);
    fclose(stdin);
}