Pagini recente » Cod sursa (job #826024) | Cod sursa (job #100862) | Cod sursa (job #1737605) | Cod sursa (job #3238097) | Cod sursa (job #405782)
Cod sursa(job #405782)
#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("replace.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("replace.out");
iesire<<nr<<"\n";
for(i=1;(i<=nr && i<=1000);++i)
iesire<<pozitii[i]<<" ";
iesire.close();
return 0;
}