Pagini recente » Cod sursa (job #1404489) | Cod sursa (job #2308840) | Cod sursa (job #1972564) | Monitorul de evaluare | Cod sursa (job #2922170)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6;
int prec[NMAX + 5];
void CalcPrec(string &s) {
int n = s.length();
int j = 0;
for(int i = 1; i < n; i++) {
while(j && s[i] != s[j])
j = prec[j - 1];
if(s[i] == s[j])
j++;
prec[i] = j;
}
}
int main()
{
string a, b;
cin >> a >> b;
int n, m;
n = a.length();
m = b.length();
CalcPrec(a);
vector<int> ans;
int i = 0;
for(int j = 0; j < m; j++) {
if(i && a[i] != b[j])
i = prec[i - 1];
if(a[i] == b[j]) {
i++;
if(i == n) {
ans.emplace_back(j - n);
i = prec[i - 1];
}
}
}
cout << ans.size() << '\n';
for(auto x : ans)
cout << x + 1 << " ";
return 0;
}