Pagini recente » Cod sursa (job #1359348) | Cod sursa (job #2058351) | Cod sursa (job #1625398) | Cod sursa (job #192041) | Cod sursa (job #2040480)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char N[2000001],H[2000001],c;
int S[2000001],p[1001];
int n,h,k,f,nr,i;
int main()
{
fi>>N+1;
n=strlen(N+1);
/// se construieste sirul S
S[0]=-1;
S[1]=0;
for ( i=2;i<=n;i++)
{
/// se calculeaza S[i]
k=i-1; //merg la ala din spate prima data
c=N[i]; //sa vad care trece de caracteru i din needle
while (N[S[k]+1]!=c && S[k]!=-1) // cat timp niciunu nu trece de caracteru c
k=S[k];//tot mergem la predecesor. se iese din while cand am gasit
S[i]=S[k]+1; //cel mai din dreapta predecesor pentru lemmingul i este cel de pe ultima poz verificata+1
}
fi>>H;
h=strlen(H);
/// algoritmul KMP
f=0;
for (i=0; i<h; i++) //rostim fiecare litera din H
{
/// bucla while pentru a detecta cel mai dinspre dreapta
/// lemming supravietuitor literei H[i]
while (f!=-1)//cat timp n-am ajuns la inceputul sirului
{
if (N[f+1]==H[i])
break; //a supravietuit
f=S[f]; //n-a supravietuit si ne intereseaza cine era inaintea lui
}
if (f==-1)
f=0; // nu supravietuieste niciunul si reluam algoritmul de la inceput, doar ca
// continuam cu rostirea literei i+1
else
{
f++; //trece de litera H[i]
if (f==n) //a ajuns la finalul lui needle
{
nr++;
if( nr<=1000)
p[nr]=i-n+1;
f=S[f]; //reluam de la cel din dreapta
}
}
}
fo<<nr<<'\n';
for( i=1; i<=nr && i<=1000; i++)
fo<<p[i]<<" ";
return 0;
}