Pagini recente » Cod sursa (job #3349342) | Cod sursa (job #3328035) | Monitorul de evaluare | Cod sursa (job #3306801) | Cod sursa (job #3310258)
//#include <iostream>
#include <fstream>
#include <set>
#include <queue>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int maxn = 2e6+5;
string a, b;
int prefix[maxn];
vector<int> answers;
signed main()
{
cin >> a >> b;
// prefix calculation
int index = -1;
prefix[0] = -1;
for(int i = 1; i < a.size(); i ++) {
while(index > 0 && a[i] != a[index + 1]) {
index = prefix[index];
}
if(a[i] == a[index + 1])
index ++;
prefix[i] = index;
}
// kmp
int idx_a = 0, idx_b = 0;
while(idx_b + a.size() - idx_a <= b.size()) {
while(idx_a < a.size() && a[idx_a] == b[idx_b]) {
idx_a ++;
idx_b ++;
}
if(idx_a == a.size())
answers.push_back(idx_b - a.size());
if(idx_a > 0) // daca ar fi 0, ar ramane tot 0, deci nu trebuie schimbar, + evitam sigsecv
idx_a = prefix[idx_a - 1] + 1;
if(idx_a == 0)
idx_b ++;
}
cout << answers.size() << '\n';
for(auto ans : answers)
cout << ans << ' ';
return 0;
}