Pagini recente » Cod sursa (job #616687) | Cod sursa (job #1032606) | Cod sursa (job #2719393) | Cod sursa (job #1752028) | Cod sursa (job #2376529)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int z[4000005];
string text, pattern, concat;
void generateZarr();
void solve() {
concat = pattern + "$" + text;
int l = concat.length();
int p = pattern.length();
generateZarr();
int nr = 0;
for (int i = 0; i < l; ++i)
if (z[i] == p)
nr++;
out << nr << '\n';
nr = 0;
for (int i = 0; i < l && nr < 1000; ++i)
if (z[i] == p) {
out << i - p - 1 << ' ';
++nr;
}
}
void generateZarr() {
int n = concat.length();
int L = 0, R = 0, k;
for (int i = 1; i < n; ++i) {
if (i > R) {
R = L = i;
while (R < n && concat[R-L] == concat[R])
R++;
z[i] = R - L;
R--;
}
else {
k = i - L;
if (z[k] < R-i+1)
z[i] = z[k];
else {
L = i;
while (R < n && concat[R-L] == concat[R])
R++;
z[i] = R - L;
R--;
}
}
}
}
int main() {
getline(in, pattern);
getline(in, text);
solve();
}