Pagini recente » Cod sursa (job #213477) | Cod sursa (job #170674) | Cod sursa (job #3286613) | Cod sursa (job #758023) | Cod sursa (job #3300141)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000005], poz[2000005];
int main() {
string a, b;
fin >> a >> b;
int m = a.size(), lung_pref = 0;
pi[0] = lung_pref;
for (int i = 1; i < m; i++) {
while (lung_pref > 0 && a[i] != a[lung_pref])
lung_pref = pi[lung_pref - 1];
if (a[i] == a[lung_pref])
lung_pref++;
pi[i] = lung_pref;
}
int n = b.size(), nr_poz = 0, nr_potriviri = 0;
lung_pref = 0;
for (int i = 0; i < n; i++) {
while (lung_pref > 0 && b[i] != a[lung_pref])
lung_pref = pi[lung_pref - 1];
if (b[i] == a[lung_pref])
lung_pref++;
if (lung_pref == m) {
nr_potriviri++;
if (nr_poz < 2000000)
poz[nr_poz++] = i - m + 1;
}
}
fout << nr_potriviri << "\n";
for (int i = 0; i < nr_poz; i++)
fout << poz[i] << " ";
fout << "\n";
return 0;
}