Pagini recente » Cod sursa (job #933814) | Cod sursa (job #5838) | Cod sursa (job #1563052) | Cod sursa (job #754536) | Cod sursa (job #3300526)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int NMAX=2*1e6+5;
int f[NMAX];
char p[NMAX], t[NMAX];
void pref(char * p, int m)
{
int i, k;
f[0]=-1;
for(i=1; i<=m; i++)
{
k=f[i-1];
while(k>=0 && p[k]!=p[i-1]) k=f[k];
f[i]=k+1;
}
}
void kmp(char * t, int n, char * p, int m)
{
int cnt=0, i=0, k=0;
int ans[1005];
while(i<=(n-m+1))
{
if(t[i+k]==p[k]) k++;
else if(k==0) i++;
else
{
i+=k-f[k];
k=f[k];
}
if(k==m)
{
cnt++;
if(cnt<=1000) ans[cnt]=i;
}
}
cout<<cnt<<'\n';
for(i=1; i<=min(cnt, 1000); i++) cout<<ans[i]<<' ';
}
int main()
{
cin>>p;
cin>>t;
int lgp=strlen(p);
pref(p, lgp);
kmp(t, strlen(t), p, lgp);
return 0;
}