Pagini recente » Cod sursa (job #757564) | Cod sursa (job #755864) | Istoria paginii utilizator/corinapop | Profil transparentul | Cod sursa (job #1019780)
/*
~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 ) ;
while( LocationLenght > PatternLenght )
{
for( int i = PatternLenght - 1; SearchLocation[i] == Pattern[i]; i-- )
if ( i == 0 )
return SearchLocation;
LocationLenght -= BadMatchTable[SearchLocation[PatternLenght - 1]];
SearchLocation += BadMatchTable[SearchLocation[PatternLenght - 1]];
}
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]);
}