Pagini recente » Cod sursa (job #226236) | Cod sursa (job #890801) | Cod sursa (job #729577) | Cod sursa (job #1538610) | Cod sursa (job #2916171)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define EFC cin.tie(nullptr)->ios_base::sync_with_stdio(false)
int d1[5] = { 0, -1, 0, 1, 0 };
int d2[5] = { 0, 0, 1, 0, -1 };
const int mod = 666013;
const int INF = 100000000;
int d11[9] = { 0 , -1, -1, 0, 1, 1, 1, 0, -1 };
int d22[9] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
int est[3] = { 0, -1, 0 };
int est1[3] = { 0, 0, 1 };
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//----------------------------------
string a, b;
vector<int> v;
int pi[1000001];
int main() {
fin >> a >> b;
int n = a.length(), m = b.length();
int k = 0;
pi[1] = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 && a[k] != a[i - 1]) {
k = pi[k];
}
if (a[k] == a[i - 1]) {
k++;
}
pi[i] = k;
}
int q = 0;
for (int i = 1; i <= m; i++) {
while (q > 0 && a[q] != b[i - 1]) {
q = pi[q];
}
if (a[q] == b[i - 1]) {
q++;
}
if (q == n) {
v.push_back(i - n);
}
}
fout << v.size() << '\n';
for (auto i : v) {
fout << i << " ";
}
}