Pagini recente » Cod sursa (job #1271254) | Cod sursa (job #1482247) | Cod sursa (job #3234449) | Cod sursa (job #3161943) | Cod sursa (job #1409250)
#include <fstream>
#include <cstring>
using namespace std;
const int kMaxL = 2000005;
char A[kMaxL], B[kMaxL];
int M, N, suff[kMaxL];
int match[1005], cnt;
void Read() {
ifstream fin("strmatch.in");
fin.getline(A + 1, kMaxL);
fin.getline(B + 1, kMaxL);
M = strlen(A + 1);
N = strlen(B + 1);
}
void MakePrefix() {
for (int i = 2, q = 0; i <= M; ++i) {
while (q && A[q + 1] != A[i])
q = suff[q];
if (A[q + 1] == A[i])
++q;
suff[i] = q;
}
}
void Search() {
for (int i = 1, q = 0; i <= N; ++i) {
while (q && A[q + 1] != B[i])
q = suff[q];
if (A[q + 1] == B[i])
++q;
if (q == M) {
if (cnt < 1000)
match[cnt] = i - M;
++cnt;
q = suff[q];
}
}
}
void Print() {
ofstream fout("strmatch.out");
fout << cnt << "\n";
for (int i = 0; i < min(cnt, 1000); ++i)
fout << match[i] << " ";
fout << "\n";
}
int main() {
Read();
MakePrefix();
Search();
Print();
return 0;
}