Pagini recente » Cod sursa (job #3231090) | Cod sursa (job #1502906) | Cod sursa (job #2619513) | Cod sursa (job #2485710) | Cod sursa (job #1923406)
#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, 2000005);
cin.get();
cin.get(t, 2000005);
}
void kmp()
{
int n = strlen(t);
int m = strlen(p);
int k = 0;
for(int i = 1; i < m; ++i)
{
while(k > 0 && p[k+1] != p[i])
k = pi[k-1];
if(p[k+1] == p[i])
++k;
pi[i] = k;
}
k = 0;
for(int i = 0; i < n; ++i)
{
while(k > 0 && p[k+1] != t[i])
k = pi[k-1];
if(p[k+1] == t[i])
++k;
if(k == m-1)
{
++ans;
if(ans <= 1000)
rez[ans] = i-m+1;
k = pi[k-1];
}
}
}
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;
}