Pagini recente » Cod sursa (job #577192) | Cod sursa (job #1237432) | Cod sursa (job #1778736) | Cod sursa (job #2303612) | Cod sursa (job #2883752)
#include <iostream>
#include <vector>
using namespace std;
int kmp[2000002];
int main ()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string key, t;
cin >> key >> t;
t = " " + key + '&' + t;
key = " " + key;
vector<int> ap;
int ans = 0;
int k = 0;
for (int i = 2; i < t.size(); i++)
{
while (k > 0 && t[k+1] != t[i])
k = kmp[k];
if (t[k+1] == t[i]) k++;
kmp[i] = k;
if (k == key.size() - 1){
ans++;
if (ans <= 1000)
{
ap.push_back(i - 2 * key.size() + 1);
}
}
}
cout << ans << '\n';
for (auto a : ap)
{
cout << a << ' ';
}
}