Pagini recente » Cod sursa (job #2213909) | Cod sursa (job #2296799) | Cod sursa (job #759413) | Cod sursa (job #1435803) | Cod sursa (job #2902428)
#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 l, r;
int size1, size2;
int readWord() {
int wordSize;
char ch;
wordSize = 0;
ch = fgetc(fin);
while ( ch != '\n' && ch != EOF ) {
v[vSize] = ch;
vSize++;
wordSize++;
ch = fgetc(fin);
}
return wordSize;
}
int calcLen(int pos) {
int i, ans;
if ( r <= pos ) {
l = r = pos;
while ( r < vSize && v[r] == v[r - l] ) {
r++;
i++;
}
r--;
ans = r - l + 1;
} else {
if ( longestPrefix[pos - l] < r - pos + 1 ) {
ans = longestPrefix[pos - l];
} else {
l = pos;
while ( r < vSize && v[r] == v[r - l] )
r++;
r--;
ans = r - pos + 1;
}
}
return ans;
}
int main() {
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
int i;
vSize = 0;
size1 = readWord();
v[vSize] = '*';
vSize++;
size2 = readWord();
ansSize = 0;
if ( size1 <= size2 ) {
l = r = 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 < min(1000, ansSize); i++ ) {
fprintf(fout, "%d ", ans[i]);
}
fclose(fin);
fclose(fout);
return 0;
}