Pagini recente » Cod sursa (job #2664265) | Cod sursa (job #229434) | Cod sursa (job #1162733) | Cod sursa (job #315253) | Cod sursa (job #2728624)
#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
// const int INF = 0x3f3f3f3f;
ifstream fin {"strmatch.in"};
ofstream fout {"strmatch.out"};
string A, B;
int N, M;
const int Nmax = 2e6+6;
int pi[Nmax];
void build_prefix() {
pi[1] = 0;
int k = 0;
for(int n = 2; n <= N; n++) {
while(k > 0 && A[k] != A[n-1]) {
k = pi[k];
}
if (A[k] == A[n-1]) { ++k; }
pi[n] = k;
}
}
int main(void) {
// freopen("strmatch.in", "r", stdin);
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
fin >> A >> B;
N = A.size();
M = B.size();
build_prefix();
int ans = 0;
vi res {};
int k = 0;
for(int i = 0; i < M; i++) {
while(k > 0 && A[k] != B[i]) {
k = pi[k];
}
if (A[k] == B[i]) { ++k; }
if (k == N) {
if (ans < 1000) {
res.push_back(i - N + 1);
}
ans++;
k = pi[N];
}
}
fout << ans << '\n';
for(auto x: res) { fout << x << ' '; }
fout << '\n';
return 0;
}