Pagini recente » Cod sursa (job #452) | Cod sursa (job #3279858) | Cod sursa (job #2376732) | Cod sursa (job #403537) | Cod sursa (job #2905713)
#include <iostream>
#define MAX_LEN 2000000
#define MAXANS 1000
using namespace std;
char str[MAX_LEN];
int strSize;
char pattern[MAX_LEN];
int patternSize;
int longestPrefixSufix[MAX_LEN];
int ans[MAXANS];
int ansSize;
FILE *fin, *fout;
void precalcLongestPrefixSufix() {
int i, i2;
longestPrefixSufix[0] = 0;
for ( i = 1; i < patternSize; i++ ) {
i2 = longestPrefixSufix[i - 1];
while ( i2 && pattern[i] != pattern[i2]) {
i2 = longestPrefixSufix[i2];
}
longestPrefixSufix[i] = i2 + (pattern[i] == pattern[i2]);
}
}
void readLine(char* v, int& sizeV) {
char ch;
sizeV = 0;
ch = fgetc(fin);
while ( ch != '\n' && ch != EOF ) {
*(v + sizeV) = ch;
sizeV++;
ch = fgetc(fin);
}
}
int main() {
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
readLine(pattern, patternSize);
readLine(str, strSize);
precalcLongestPrefixSufix();
int i, i2;
i = i2 = 0;
while ( i < strSize ) {
if ( str[i] == pattern[i2] ) {
i2++;
i++;
if ( i2 == patternSize ) {
if ( ansSize < 1000 )
ans[ansSize] = i - patternSize;
ansSize++;
}
} else {
if ( i2 > 0 )
i2 = longestPrefixSufix[i2 - 1];
else
i++;
}
}
fprintf(fout, "%d\n", ansSize);
for ( i = 0; i < min(ansSize, 1000); i++ ) {
fprintf(fout, "%d ", ans[i]);
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}