Pagini recente » Cod sursa (job #2161855) | Cod sursa (job #545627) | Cod sursa (job #2513947) | Cod sursa (job #18388) | Cod sursa (job #953269)
Cod sursa(job #953269)
#include <fstream>
#include <cstring>
using namespace std;
int d[200005];
int pref[200005];
char a[200005],b[200005];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int n1,n2,i;
cin.get(a,200005);
cin.get();
cin.get(b,200005);
n1=strlen(a);
n2=strlen(b);
#define pref (pref-1)
#define a (a-1)
#define b (b-1)
pref[1]=0;
int k=0;
for(i=2;i<=n1;i++)
{
//k=pref[i-1];
while(k>0 && a[k+1]!=a[i])
k=pref[k];
if(a[k+1]==a[i])
k++;
pref[i]=k;
}
//cout<<"da"<<endl;
int poz=0;
k=0;
for(i=1;i<=n2;i++)
{
while(k>0 && a[k+1]!=b[i])
k=pref[k];
if(a[k+1]==b[i])
k++;
if(k==n1)
{
d[poz++]=i-n1;
k=pref[k];
}
}
cout<<poz<<'\n';
if(poz>1000)
poz=1000;
for(i=0;i<poz;i++)
cout<<d[i]<<' ';
cout<<'\n';
cin.close();
cout.close();
return 0;
}