Pagini recente » Cod sursa (job #2321263) | Cod sursa (job #2536431) | Cod sursa (job #3148126) | Cod sursa (job #2777801) | Cod sursa (job #2682070)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int pi[2000005];
vi sol;
void make_prefix() {
pi[0] = 0;
int q = 0;
for (int i = 1; i < a.size(); i++) {
while (q && a[q] != a[i])
q = pi[q];
if (a[q] == a[i])
q++;
pi[i] = q;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
fin >> a >> b;
make_prefix();
int q = 0;
int count = 0;
for (int i = 0; i < b.size(); i++) {
while (q && a[q] != b[i])
q = pi[q];
if (a[q] == b[i])
q++;
if (q == a.size()) {
q = pi[a.size() - 1];
count++;
if (count <= 1000) {
sol.pb(i - a.size() + 1);
}
}
}
fout << count << "\n";
for (auto s : sol) {
fout << s << " ";
}
fout << "\n";
return 0;
}