Pagini recente » Cod sursa (job #2979347) | Cod sursa (job #1607167) | Cod sursa (job #3121011) | Cod sursa (job #555520) | Cod sursa (job #2913987)
// Z-Prefix
#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 M = S.size();
T = S + '#' + T;
int N = T.size();
vector<int> Z(N), res;
int ans = 0;
for(int i = 1, x = 0, y = 0; i < N; i++) {
Z[i] = y < i ? 0 : min(Z[i-x], y-i+1);
while(i+Z[i] < N && T[i+Z[i]] == T[Z[i]]) Z[i]++;
if (i+Z[i]-1 > y) {
x = i, y = i+Z[i]-1;
}
if (i > M && Z[i] == M) {
if (ans < 1000)
res.push_back(i-M-1);
ans++;
}
}
cout << ans << "\n";
for(auto x : res) cout << x << " ";
cout << "\n";
return 0;
}