Pagini recente » Cod sursa (job #2205707) | Cod sursa (job #2422252) | Cod sursa (job #2911707) | Cod sursa (job #32962) | Cod sursa (job #2376496)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int z[2000005];
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';
for (int i = 0; i < l; ++i)
if (z[i] == p)
out << i - p - 1 << ' ';
}
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();
}