Pagini recente » Cod sursa (job #2055759) | Cod sursa (job #2854974) | Cod sursa (job #1381589) | Cod sursa (job #218580) | Cod sursa (job #2481164)
#include <iostream>
#include <stdio.h>
#include <ctype.h>
using namespace std;
const int NMAX = 2 * 1e6;
int kmp[NMAX * 2 + 2];
char s[NMAX * 2 + 2];
int main() {
FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );
int i, k, x, total;
i = 1;
fscanf( fin, " " );
char ch = fgetc( fin );
while ( isalpha( ch ) || isdigit( ch ) ) {
s[i] = ch;
ch = fgetc( fin );
i ++;
}
k = i - 1;
s[i] = '#';
i ++;
fscanf( fin, " " );
ch = fgetc( fin );
while ( isalpha( ch ) || isdigit( ch ) ) {
s[i] = ch;
ch = fgetc( fin );
i ++;
}
int n = i - 1;
for ( i = 2; i <= n; i ++ ) {
x = kmp[i - 1];
while ( x > 0 && s[x + 1] != s[i] )
x = kmp[x];
if ( s[i] == s[x + 1] )
kmp[i] = x + 1;
}
total = 0;
for ( i = k; i <= n; i ++ ) {
if ( kmp[i] == k ) {
total ++;
}
}
fprintf( fout, "%d\n", total );
i = k;
if ( total > 1000 )
total = 1000;
while ( i <= n && total > 0 ) {
if ( kmp[i] == k ) {
total --;
fprintf( fout, "%d ", i - 2 * k - 1 );
}
i ++;
}
fclose( fin );
fclose( fout );
return 0;
}