Pagini recente » Rating Teodora Resmerita (teodoraresmerita) | Rating Balan Catalin (Catal) | Rating Necsoiu Madalina (MadalinaNec) | Cod sursa (job #3289912) | Cod sursa (job #1998249)
#include<fstream>
#include<string.h>
#define MAXLEN 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[MAXLEN], B[MAXLEN];
int prefix[MAXLEN], matches[MAXLEN], lMatches;
void buildPrefixArray(int *prefix, char *A) {
//
int crt = 0;
int l = strlen(A);
prefix[0] = 0;
for (int i = 1; i < l; i++) {
int len = prefix[i - 1];
while (len != 0 && A[len] != A[i]) {
len = prefix[len - 1];
}
if (A[len] == A[i]) prefix[i] = len + 1;
}
}
void printMatches(int prefix[], char A[], char B[], int matches[], int &lMatches) {
//
int crt = 0;
int lB = strlen(B);
int lA = strlen(A);
lMatches = 0;
int len = 0;
for (int i = 0; i < lB; i++) {
//
while (len != 0 && A[len] != B[i]) {
len = prefix[len - 1];
}
if (A[len] == B[i]) len++;
if (len == lA) {
matches[++lMatches] = i - lA + 1;
len = prefix[len - 1];
}
}
}
int main() {
//
f >> A;
f >> B;
buildPrefixArray(prefix, A);
printMatches(prefix, A, B, matches, lMatches);
g << lMatches << endl;
lMatches = lMatches > 1000 ? 1000 : lMatches;
for (int i = 1; i <= lMatches; i++)
g << matches[i] << " ";
return 0;
}