Pagini recente » Atasamentele paginii Profil vasi_kosminski | Atasamentele paginii Profil Magnani_Patrick | Atasamentele paginii Profil bogdan_gati | Statistici Stoica Liviu (RamsesTK) | Cod sursa (job #3365871)
//KMP
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
int n,m,i,j,nr,pi[2000005],rez[1005];
string a,b;
int main()
{
cin>>a>>b;
n=a.size();
m=b.size();
j=0;
for(i=1; i<n; i++)
{
while(j>0 && a[i]!=a[j]) j=pi[j-1];
if(a[i]==a[j]) j++;
pi[i]=j;
}
j=0;
nr=0;
for(i=0; i<m; i++)
{
while(j>0 && b[i]!=a[j]) j=pi[j-1];
if(b[i]==a[j]) j++;
if(j==n)
{
nr++;
if(nr<=1000) rez[nr]=i-n+1;
j=pi[j-1];
}
}
cout<<nr<<'\n';
for(i=1; i<=min(nr,1000); i++)
cout<<rez[i]<<' ';
return 0;
}