Pagini recente » Cod sursa (job #2842075) | Cod sursa (job #455198) | Cod sursa (job #2809120) | Cod sursa (job #2641423) | Cod sursa (job #2985244)
#include <bits/stdc++.h>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int lg1,j,i,tata[2000008],aux,ras[1008],cnt,poz,lg2;
char cuv1[2000008],cuv2[2000008];
int main()
{
cin>>cuv1+1;
lg1=strlen(cuv1+1);
aux=0;
tata[1]=0;
for(i=2;i<=lg1;i++)
{
j=tata[i-1];
while(cuv1[j+1]!=cuv1[i] && j!=0)
{
j=tata[j];
}
if(cuv1[j+1]==cuv1[i])
tata[i]=j+1;
else
tata[i]=0;
}
poz=0;
cin>>cuv2+1;
lg2=strlen(cuv2+1);
for(i=1;i<=lg2;i++)
{
while(cuv2[i]!=cuv1[poz+1] && poz!=0)
{
poz=tata[poz];
}
if(cuv2[i]==cuv1[poz+1])
poz++;
else
poz=0;
if(poz>=lg1)
{
if(cnt<1000)
ras[++cnt]=i-lg1;
else
cnt++;
}
}
cout<<cnt<<'\n';
for(i=1;i<=min(1000,cnt);i++)
{
cout<<ras[i]<<" ";
}
return 0;
}