Pagini recente » Cod sursa (job #1460756) | Cod sursa (job #893004) | Cod sursa (job #903193) | Cod sursa (job #2989127) | Cod sursa (job #1019797)
/*
~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);
}