Pagini recente » Cod sursa (job #1807342) | Cod sursa (job #1358286) | Cod sursa (job #866167) | Cod sursa (job #564155) | Cod sursa (job #2263579)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream in ( "strmatch.in" );
ofstream out ( "strmatch.out" );
const int N_MAX = 2000005;
char a[N_MAX], b[N_MAX];
int n, m;
int pref_suf[N_MAX];
int rez[N_MAX], k;
void creaza_pref_suf() {
pref_suf[0] = 0;
int lg { 0 };
for (int i { 1 }; i < n;) {
if (a[i] == a[lg]) {
pref_suf[i++] = ++lg;
} else {
if (lg) {
lg = pref_suf[lg - 1];
} else {
pref_suf[i] = 0;
++i;
}
}
}
}
void KMP() {
for (int i { 0 }, j { 0 }; i < m;) {
if (b[i] == a[j]) {
++i;
++j;
}
if (j == n)
rez[k++] = i - j;
if (i < m && a[j] != b[i]) {
if (j)
j = pref_suf[j - 1];
else
++i;
}
}
}
int main() {
in.getline(a, N_MAX);
in.getline(b, N_MAX);
n = strlen(a);
m = strlen(b);
if (n > m) {
out << 0;
return 0;
}
creaza_pref_suf();
KMP();
out << k << '\n';
k = min(1000, k);
for (int i { 0 }; i < k; ++i)
out << rez[i] << ' ';
}