Pagini recente » Cod sursa (job #1473426) | Cod sursa (job #268350) | Cod sursa (job #518511) | Cod sursa (job #1074884) | Cod sursa (job #2905476)
// Mihai Priboi
#include <bits/stdc++.h>
using namespace std;
#define MAXN 4000000
int z[MAXN];
char s[MAXN];
int sSize, pSize;
int rez;
void computeZ() {
int l, r, i;
l = r = 0;
for( i = 0; i < sSize && rez < 1000; i++ ) {
if( i > r ) {
l = r = i;
while( r < sSize && s[r - i] == s[r] ) r++;
r--;
z[i] = r - l + 1;
}
else {
if( z[i - l] < r - i + 1 )
z[i] = z[i - l];
else {
l = i;
while( r < sSize && s[r - i] == s[r] ) r++;
r--;
z[i] = r - l + 1;
}
}
if( z[i] == pSize ) rez++;
}
}
int main() {
FILE *fin, *fout;
int i;
fin = fopen( "strmatch.in", "r" );
fscanf( fin, "%s\n", s );
pSize = strlen(s);
fscanf( fin, "%s", s + pSize + 1 );
fclose( fin );
s[pSize] = '$';
sSize = strlen(s);
computeZ();
fout = fopen( "strmatch.out", "w" );
fprintf( fout, "%d\n", rez );
for( i = pSize + 1; i < sSize && rez > 0; i++ ) {
if( z[i] == pSize ) {
fprintf( fout, "%d ", i - pSize - 1 );
rez--;
}
}
fclose( fout );
return 0;
}