Pagini recente » Cod sursa (job #2415208) | Cod sursa (job #757959) | Cod sursa (job #376791) | Cod sursa (job #1691306) | Cod sursa (job #3263605)
#include <bits/stdc++.h>
using namespace std;
int Z[4000005];
void buildZ(string &a) {
Z[0] = 0;
int best = 0; // cel mai bun Z so far
for (int i = 1; i < a.length(); i++) {
if (i <= best + Z[best] - 1) { // daca i ul se afla in interiorul celui mai bun Z de pana acum
Z[i] = min(best + Z[best] - i, Z[i - best]);
}
while (a[i + Z[i]] == a[Z[i]]) {
Z[i]++;
}
if (best + Z[best] < i + Z[i]) {
best = i;
}
}
}
signed main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string a, b;
cin >> a >> b;
int counter = 0;
vector <int> pos;
int targetSize = a.size();
a += '$';
a += b;
buildZ(a);
for (int i = 0; i < a.size(); i++) {
if (Z[i] == targetSize) {
counter += 1;
if (pos.size() == 1000) continue;
pos.push_back(i - targetSize - 1);
}
}
cout << counter << '\n';
for (auto x : pos) {
cout << x << ' ';
}
}