Pagini recente » Cod sursa (job #567119) | Diferente pentru problema/beyond_the_wall intre reviziile 1 si 2 | Cod sursa (job #3349308) | Cod sursa (job #1494020) | Cod sursa (job #3310263)
//#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() - 1 - idx_a < b.size()) {
while(idx_a < a.size() && idx_b < b.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)
idx_a = prefix[idx_a - 1] + 1;
else
{
idx_b ++;
}
}
cout << answers.size() << '\n';
for(int i = 0; i < min(1000, (int)answers.size()); i ++)
cout << answers[i] << ' ';
return 0;
}