Pagini recente » Cod sursa (job #1311270) | Cod sursa (job #774569) | Cod sursa (job #115730) | Cod sursa (job #1459629) | Cod sursa (job #2190751)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 4e6 + 10;
int Z[NMAX];
char AB[NMAX];
int main() {
assert(freopen("strmatch.in", "r", stdin));
assert(freopen("strmatch.out", "w", stdout));
cin >> AB;
int lenA = strlen(AB);
cin >> (AB + lenA + 1);
int lenB = strlen(AB + lenA + 1);
int lenAB = lenA + lenB + 1;
Z[0] = lenAB;
int left = -1, right = -1;
for (int i = 1; i < lenAB; ++i) {
if (i >= left && i <= right) {
int matchSize = Z[i - left];
if (i + matchSize - 1 < right) {
Z[i] = matchSize;
} else {
while (AB[i + matchSize] == AB[matchSize])
++matchSize;
Z[i] = matchSize;
if (i + matchSize - 1 > right) {
left = i;
right = i + matchSize - 1;
}
}
} else {
int matchSize = 0;
while (AB[i + matchSize] == AB[matchSize])
++matchSize;
Z[i] = matchSize;
left = i;
right = i + matchSize - 1;
}
}
vector<int> answer;
for (int i = lenA + 1; i < lenAB && answer.size() < 1000; ++i) {
if (Z[i] == lenA)
answer.push_back(i - lenA - 1);
}
cout << answer.size() << '\n';
for (int i: answer)
cout << i << ' ';
cout << '\n';
return 0;
}