Pagini recente » Cod sursa (job #455190) | Borderou de evaluare (job #2017430) | Borderou de evaluare (job #88812) | Monitorul de evaluare | Cod sursa (job #2909750)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAXX 2000000
#define INVALID_CHAR '$'
#define MATCHMAXX 1000
using namespace std;
int z[NMAXX * 2 + 1], match[MATCHMAXX + 1];
char str[NMAXX * 2 + 1];
int strSize;
void computeZ() {
int i, left, right;
left = right = 0;
for ( i = 1; i < strSize; i++ ) {
if ( z[i - left] < right - i + 1)
z[i] = z[i - left];
else {
left = i;
if ( i > right )
right = i;
while ( right < strSize && str[right - left] == str[right] )
right++;
right--;
z[i] = right - left + 1;
}
}
}
int main() {
FILE *fin, *fout;
int patternSize, i, nrmatch;
fin = fopen( "strmatch.in", "r" );
fout = fopen( "strmatch.out", "w" );
fscanf( fin, "%s\n", str );
patternSize = strlen( str );
str[patternSize] = INVALID_CHAR;
fscanf( fin, "%s", str + patternSize + 1 );
strSize = strlen( str );
computeZ();
nrmatch = 0;
for ( i = 0; i < strSize; i++ ) {
if ( z[i] == patternSize ) {
if ( nrmatch < MATCHMAXX )
match[nrmatch] = i - patternSize - 1;
nrmatch++;
}
}
fprintf( fout, "%d\n", nrmatch );
nrmatch = min( nrmatch, MATCHMAXX );
for ( i = 0; i < nrmatch; i++ )
fprintf( fout, "%d ", match[i] );
fclose( fin );
fclose( fout );
return 0;
}