Pagini recente » Cod sursa (job #1558898) | Cod sursa (job #1672918) | Profil UTI_Gilca_Gheorghita_Nutu | Cod sursa (job #2488459) | Cod sursa (job #991931)
Cod sursa(job #991931)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAX = 2000100;
char a[MAX], b[MAX];
int l1, l2, q;
int sol, soln[1010];
int pi[MAX];
int main() {
fin.getline(a + 1, MAX - 1);
fin.getline(b + 1, MAX - 1);
l1 = strlen(a + 1);
l2 = strlen(b + 1);
q = 0;
for (int i = 2; i <= l1; ++i) {
while (q > 0 && a[i] != a[q + 1])
q = pi[q];
if (a[i] == a[q + 1])
++q;
pi[i] = q;
}
q = 0;
for (int i = 1; i <= l2; ++i) {
while (q > 0 && b[i] != a[q + 1])
q = pi[q];
if (b[i] == a[q + 1])
++q;
if (q == l1) {
++sol;
if (sol <= 1000) {
soln[sol] = i - l1 + 1;
}
q = pi[q];
}
}
fout << sol << '\n';
for (int i = 1; i <= sol; ++i)
fout << soln[i] - 1 << ' ';
}