Pagini recente » Cod sursa (job #2752883) | Cod sursa (job #2592617) | Cod sursa (job #933393) | Cod sursa (job #1371269) | Cod sursa (job #2913985)
// Knuth-Morris-Pratt
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
int main(void) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string S, T;
cin >> S >> T;
int N = S.size();
vector<int> p(N);
for(int i = 1, k = 0; i < N; i++) { // invariant: k = p[i-1] -- longest prefix
while(k && S[i] != S[k]) k = p[k-1];
if (S[i] == S[k]) k++;
p[i] = k;
}
int ans = 0;
vector<int> res;
for(int i = 0, k = 0; i < (int)T.size(); i++) { // k = p[i-1]
while(k && T[i] != S[k]) k = p[k-1];
if (T[i] == S[k]) k++;
if (k == N) {
if (ans < 1000)
res.push_back(i - N +1);
ans++;
k = p[N-1];
}
}
cout << ans << "\n";
for(auto x: res) cout << x << " ";
cout << "\n";
return 0;
}