Pagini recente » Cod sursa (job #1709092) | Cod sursa (job #1044154) | Cod sursa (job #1735636) | Cod sursa (job #2033327) | Cod sursa (job #2675091)
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001], b[2000001];
int sol[1001], p[2000001], m, n;
int matchS() {
int k = 0, nr = 0;
for (int i = 1; i <= n; i++) {
while (k > 0 && a[k + 1] != b[i])
k = p[k];
if (b[i] == a[k + 1])
k++;
if (k == m) {
nr++;
if (nr <= 1000)
sol[nr] = i - m;
k = p[k];
}
}
return nr;
}
void afisare(int nr) {
g << nr << '\n';
nr = min(nr, 1000);
for (int i = 1; i <= nr; i++)
g << sol[i] << ' ';
}
void rezolvare() {
int k = 0;
p[1] = 0;
for (int j = 2; j <= m; j++) {
while (k > 0 && a[k + 1] != a[j])
k = p[k];
if (a[k + 1] == a[j]) {
k++;
}
p[j] = k;
}
}
void citire() {
f.getline(a + 1, NMAX);
f.getline(b + 1, NMAX);
n = strlen(b + 1);
m = strlen(a + 1);
}
int main() {
rezolvare();
int nr = matchS();
afisare(nr);
return 0;
}