Pagini recente » Cod sursa (job #2849506) | Cod sursa (job #1105374) | Cod sursa (job #278386) | Cod sursa (job #871016) | Cod sursa (job #2040132)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s, one, two;
vector<int> z(4000100);
vector<int> pos;
void make_s() {
cin >> one >> two;
s += ' ';
s += one;
s += '#';
s += two;
}
void solve() {
int cont = 0;
int C = 0, R = 0;
for (int i = 2; i < s.size(); i++) {
z[i] = max(min(z[i - C], R - i), 0);
while (s[z[i] + 1] == s[i + z[i] + 1]) {
z[i]++;
}
if (z[i] == one.size()) {
cont++;
if (cont <= 1000) {
pos.push_back(i - one.size() - 1);
}
}
if (R < i + z[i]){
R = i + z[i];
C = i;
}
}
cout << cont << '\n';
for (auto &x : pos) {
cout << x << " ";
}
}
int main() {
make_s();
solve();
return 0;
}