Pagini recente » Cod sursa (job #534871) | Cod sursa (job #2921384) | Cod sursa (job #783939) | Cod sursa (job #1668914) | Cod sursa (job #405785)
Cod sursa(job #405785)
#include <fstream>
#include <string.h>
using namespace std;
#define MAX 2000010
char sir1[MAX],sir2[MAX];
long daubine[MAX],lungime1,lungime2,pozitii[1010],nr,q,i;
void prefix()
{
q=0;
daubine[1]=0;
for(i=2;i<=lungime1;++i)
{
while(q && sir1[q+1]!=sir1[i])
q=daubine[q];
if(sir1[q+1]==sir1[i])
++q;
daubine[i]=q;
}
}
void kmp()
{
nr=0;
q=0;
for(i=1;i<=lungime2;++i)
{
while(q && sir1[q+1]!=sir2[i])
q=daubine[q];
if(sir1[q+1]==sir2[i])
++q;
if(q==lungime1)
{
++nr;
if(nr<=1000) pozitii[nr]=i-lungime1;
q=daubine[q];
}
}
}
int main()
{
ifstream intrare("strmatch.in");
intrare>>sir1+1;
intrare>>sir2+1;
intrare.close();
sir1[0]=' ';
sir2[0]=' ';
lungime1=strlen(sir1)-1;
lungime2=strlen(sir2)-1;
prefix();
kmp();
ofstream iesire("strmatch.out");
iesire<<nr<<"\n";
for(i=1;(i<=nr && i<=1000);++i)
iesire<<pozitii[i]<<" ";
iesire.close();
return 0;
}