Pagini recente » Cod sursa (job #2710979) | Cod sursa (job #1480089) | Cod sursa (job #583491) | Cod sursa (job #2149003) | Cod sursa (job #2735714)
#include <bits/stdc++.h>
#define ll long long
#define cin fin
#define cout fout
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int lps[2000004];
int main() {
cin >> a >> b;
for (int i = 1; i < a.size(); ) {
int curr = 0;
if (a[i] == a[0]) {
int add = 0;
while (a[i] == a[add]) {
add++;
lps[++i] = add;
}
} else
lps[++i] = 0;
}
a = " " + a;
b = " " + b;
vector <int> positions;
int curr = 0, res = 0;
for (int i = 1; i < b.size(); ) {
while (b[i] == a[curr + 1] && curr < a.size() && i < b.size()) {
i++;
curr++;
}
if (curr == a.size() - 1) {
curr = lps[curr];
positions.push_back(i - (int)a.size());
} else if (curr)
curr = lps[curr];
else
i++;
}
cout << positions.size() << '\n';
for (int i : positions)
cout << i << ' ';
}