Pagini recente » Cod sursa (job #2057688) | Cod sursa (job #2683979) | Cod sursa (job #1832076) | Cod sursa (job #2227066) | Cod sursa (job #1745966)
# include <iostream>
# include <fstream>
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <vector>
# include <cstring>
using namespace std;
# define MAX_LEN 2000001
int pi[MAX_LEN];
char a[1 + MAX_LEN];
char b[1 + MAX_LEN];
int rez[1000];
int main() {
FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );
int i, k, r, n, m, s;
fgets( a + 1, MAX_LEN, fin );
fgets( b + 1, MAX_LEN, fin );
n = strlen( a + 1 );
m = strlen( b + 1 );
n -= ( a[n] == '\n' );
m -= ( a[m] == '\n' );
pi[0] = -1;
k = r = s = 0;
for ( i = 1; i <= m; i ++ ) {
while ( k != -1 && b[i] != a[k + 1] )
k = pi[k];
k ++;
pi[i] = k;
if ( k == n ) {
if ( s < 1000 )
rez[s] = i - n;
s ++;
}
}
fprintf( fout, "%d\n", s );
for ( i = 0; i < s && i < 1000; i ++ )
fprintf( fout, "%d ", rez[i] );
fclose( fin );
fclose( fout );
return 0;
}