Pagini recente » Cod sursa (job #1080604) | Cod sursa (job #398666) | Cod sursa (job #867688) | Cod sursa (job #3207065) | Cod sursa (job #1932446)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long n,m,incadrari=0,gasit,i,j;
string sir1,sir2;
vector <int> pozitii(1000);
vector <int> sufix(2000000,0);
void calcul_prefix()
{
j=0;
for(i=1;i<n;i++)
{
while(j>0&&sir1[i]!=sir1[j])
j=sufix[j-1];
if(sir1[i]==sir1[j])
{
sufix[i]=j+1;
j++;
}
}
}
void gasire_sir()
{
i=0;
for( j=0;j<m;j++)
{
while(i>0&&sir1[i]!=sir2[j])
i=sufix[i-1];
if(sir1[i]==sir2[j])
i++;
if(i==n)
{
if(incadrari<1000)
pozitii[incadrari]=j-i+1;
incadrari++;
}
}
}
void KMP()
{
i=1,j=0;
calcul_prefix();
gasire_sir();
g<<incadrari<<"\n";
for(i=0;i<incadrari&&i<1000;i++)
g<<pozitii[i]<<" ";
}
int main()
{
f>>sir1>>sir2;
n=sir1.size();
m=sir2.size();
KMP();
f.close();g.close();
}