Pagini recente » Cod sursa (job #2754422) | Cod sursa (job #1321754) | Cod sursa (job #3189308) | Cod sursa (job #1411152) | Cod sursa (job #2748398)
#include <iostream>
#include <fstream>
#include <string>
const int NMAX = 1e6;
const int MAX_AP = 1e3;
std::string a, b;
int pi[1 + 2 * NMAX];
int sol_size;
int sol[1 + MAX_AP];
int main() {
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
in >> a >> b;
const int target = a.size();
a = "." + a + "." + b;
int k = 0;
pi[1] = 0;
for (int i = 2; i < a.size(); ++i) {
while (k > 0 && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
++k;
pi[i] = k;
if (k == target) {
++sol_size;
if (sol_size <= MAX_AP)
sol[sol_size] = i - 2 * target - 1;
}
}
out << sol_size << '\n';
for (int i = 1; i <= sol_size && i <= MAX_AP; ++i)
out << sol[i] << ' ';
out << '\n';
return 0;
}