Pagini recente » Cod sursa (job #2680446) | Cod sursa (job #900286) | Cod sursa (job #1190325) | Cod sursa (job #1187210) | Cod sursa (job #2339668)
//
// main.cpp
// strmatch
//
// Created by Octavian Custura on 09/02/2019.
// Copyright © 2019 Octavian Custura. All rights reserved.
//
#include <fstream>
#include <cstring>
int main() {
std::ifstream fin ("strmatch.in");
std::ofstream fout ("strmatch.out");
char s[2000001], t[2000001];
int sol[1001], p[200001];
fin >> (s + 1);
fin >> (t + 1);
int n = strlen(s + 1);
int m = strlen(t + 1);
int L = 0;
p[1] = 0;
for (int i = 2; i <= n; ++i) {
while (L != 0 && s[i] != s[L + 1]) {
L = p[L];
}
if (s[i] == s[L + 1]) {
L++;
}
p[i] = L;
}
L = 0;
int ap = 0;
for (int i = 1; i <= m; ++i) {
while (L != 0 && t[i] != s[L + 1]) {
L = p[L];
}
if (t[i] == s[L + 1]) {
L++;
}
if (L == n) {
ap++;
if (ap <= 1000) {
sol[ap] = i - n;
}
L = p[L];
}
}
fout << ap << '\n';
if (ap > 1000) {
ap = 1000;
}
for (int i = 1; i <= ap; ++i) {
fout << sol[i] << ' ';
}
return 0;
}