Pagini recente » Cod sursa (job #805814) | Cod sursa (job #510992) | Cod sursa (job #1726607) | Cod sursa (job #1288039) | Cod sursa (job #2271278)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int sza, szb, phi[2000100], ans, sol[2000100], vf;
void KMP() {
int i = 1, j = 2;
while (j <= sza) {
while (i > 1 && a[j] != a[i])
i = phi[i - 1] + 1;
if (a[i] == a[j])
phi[j] = i++;
j++;
}
}
void match() {
int i = 1, j = 1;
while (j <= szb) {
while (i > 1 && b[j] != a[i])
i = phi[i - 1] + 1;
if (a[i] == b[j])
i++;
if (i > sza)
sol[++vf] = j - sza;
j++;
}
out << vf << '\n';
for (int i = 1; i <= min(vf, 1000); i++)
out << sol[i] << ' ';
}
int main() {
in >> a >> b;
sza = a.size();
szb = b.size();
a = '+' + a;
b = '+' + b;
KMP();
match();
return 0;
}