Pagini recente » Cod sursa (job #1738643) | Cod sursa (job #2005732) | Cod sursa (job #842214) | Cod sursa (job #1474733) | Cod sursa (job #1661650)
#include<iostream>
#include<fstream>
#include<cstring>
#define DX 2000009
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
char x[DX],y[DX];
int lx,ly,pr[DX],r[1010],lr;
void sp()
{
int poz=0,i,j;
for(i=2;i<=lx;i++)
{
while(poz && x[poz+1]!=x[i])
poz=pr[poz];
if(x[poz+1]==x[i])
poz++;
pr[i]=poz;
}
}
int main()
{
int i,j,poz=0,total=0;
fin>>x>>y;
lx=strlen(x);
ly=strlen(y);
for(i=lx;i>0;i--) x[i]=x[i-1];
for(i=ly;i>0;i--) y[i]=y[i-1];
sp();
//for(i=1;i<=lx;i++) cout<<pr[i]<<" ";
for(i=1;i<=ly;i++)
{
while(poz && x[poz+1]!=y[i])
poz=pr[poz];
if(x[poz+1]==y[i])
poz++;
if(poz==lx)
{
total++;
poz=pr[poz];
if(lr<1000) r[++lr]=i-lx;
}
}
fout<<" total: "<<total<<"\n";
for(i=1;i<=lr;i++) fout<<r[i]<<" ";
}