Pagini recente » Cod sursa (job #3147097) | Cod sursa (job #2196245) | Cod sursa (job #1449357) | Cod sursa (job #1413867) | Cod sursa (job #2883756)
#include <iostream>
#include <vector>
using namespace std;
int kmp[4002002];
int main ()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string key, t; cin >> key >> t;
t = " " + key + '$' + t;
key = " " + key;
int k = 0;
int ans = 0;
vector<int> ap;
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 << ' ';
}
}