Pagini recente » Cod sursa (job #1671517) | Cod sursa (job #2209616) | Cod sursa (job #2719497) | Cod sursa (job #1872319) | Cod sursa (job #1923409)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char p[2000005], t[2000005];
int pi[2000005], rez[1005], ans;
void citeste()
{
cin.get(p+1, 2000005);
cin.get();
cin.get(t+1, 2000005);
}
void kmp()
{
int n = strlen(t+1);
int m = strlen(p+1);
int k = 0;
for(int i = 2; i <= m; ++i)
{
while(k > 0 && p[k+1] != p[i])
k = pi[k];
if(p[k+1] == p[i])
++k;
pi[i] = k;
}
k = 0;
for(int i = 1; i <= n; ++i)
{
while(k > 0 && p[k+1] != t[i])
k = pi[k];
if(p[k+1] == t[i])
++k;
if(k == m)
{
++ans;
if(ans <= 1000)
rez[ans] = i-m;
k = pi[k];
}
}
}
void afis()
{
cout << ans << '\n';
for(int i = 1; i <= min(ans, 1000); ++i)
cout << rez[i] << ' ';
}
int main()
{
ios_base::sync_with_stdio(false);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citeste();
kmp();
afis();
return 0;
}