Pagini recente » Cod sursa (job #20362) | Unirea 2007, Clasament pentru clasele IX-X | Cod sursa (job #1650676) | Cod sursa (job #1284820) | Cod sursa (job #3170457)
#include <bits/stdc++.h>
#define MAXSZ 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, p[MAXSZ] = {0};
char a[MAXSZ], b[MAXSZ];
int main() {
fin >> b >> a;
n = (int) strlen(a);
m = (int) strlen(b);
p[0] = 0;
p[1] = 0;
int q = 0;
for (int i = 2; i <= m; i++) {
while (q > 0 && b[q] != b[i - 1])
q = p[q];
if (b[q] == b[i - 1])
q++;
p[i] = q;
}
int j = 0;
vector<int> matches;
for (int i = 0; i < n; i++) {
while (j > 0 && a[i] != b[j])
j = p[j];
if (a[i] == b[j])
j++;
if (j == m) {
matches.push_back(i - m + 1);
j = p[j];
}
}
fout << matches.size() << '\n';
for (auto& i: matches)
fout << i << ' ';
}