Cod sursa(job #1020366)

Utilizator taigi100Cazacu Robert taigi100 Data 1 noiembrie 2013 23:40:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 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 - 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 )
    {
		if( MatchesNumber < 1000 )
        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);
}