Pagini recente » Cod sursa (job #1207528) | Cod sursa (job #859405) | Cod sursa (job #620405) | Cod sursa (job #162205) | Cod sursa (job #2902406)
#include <iostream>
#define MAX_LEN 2000000
using namespace std;
FILE *fin, *fout;
char v[MAX_LEN * 2 + 1];
int vSize;
int ans[MAX_LEN];
int ansSize;
int longestPrefix[MAX_LEN * 2 + 1];
int lef, righ;
int readWord() {
int wordSize;
char ch;
wordSize = 0;
ch = fgetc(fin);
while ( 'A' <= ch && ch <= 'Z' ) {
v[vSize] = ch;
vSize++;
wordSize++;
ch = fgetc(fin);
}
return wordSize;
}
int calcLen(int pos) {
int i, ans;
if ( righ <= pos ) {
lef = righ = pos;
while ( righ < vSize && v[righ] == v[righ - lef] ) {
righ++;
i++;
}
righ--;
ans = righ - lef + 1;
} else {
if ( longestPrefix[pos - lef] <= righ - pos + 1 ) {
ans = longestPrefix[pos - lef];
} else {
while ( righ < vSize && v[righ] == v[righ - lef] )
righ++;
righ--;
lef = pos;
ans = righ - pos + 1;
}
}
return ans;
}
int main() {
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
int size1, size2, i;
vSize = 0;
size1 = readWord();
v[vSize] = '*';
vSize++;
size2 = readWord();
ansSize = 0;
if ( size1 <= size2 ) {
lef = righ = 0;
for ( i = 1; i < vSize; i++ ) {
longestPrefix[i] = calcLen(i);
if ( longestPrefix[i] == size1 && i > size1 ) {
if ( ansSize <= 1000 )
ans[ansSize] = i - size1 - 1;
ansSize++;
}
}
}
fprintf(fout, "%d\n", ansSize);
for ( i = 0; i < ansSize; i++ ) {
fprintf(fout, "%d ", ans[i]);
}
fclose(fin);
fclose(fout);
return 0;
}