Pagini recente » Cod sursa (job #3359202) | Cod sursa (job #3359020) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3359153)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 4'000'000;
int kmp[NMAX];
int ans[NMAX];
void makekmp(string &s) {
for(int i = 1; i < s.size(); i ++) {
int j = kmp[i - 1];
while(j > 0 && s[i] != s[j]) {
j = kmp[j - 1];
}
if(s[i] == s[j])
j ++;
kmp[i] = j;
}
}
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin.tie(0)->sync_with_stdio(0);
string a, b; cin >> a >> b;
string c = a + '#' + b;
makekmp(c);
int sz = 0;
for(int i = a.size(); i < c.size(); i ++) {
if(kmp[i] == a.size()) {
ans[sz ++] = i - 2 * a.size();
}
}
cout << sz << '\n';
sz = min(sz, 1000);
for(int i = 0; i < sz; i ++) {
cout << ans[i] << ' ';
}
}