Pagini recente » Cod sursa (job #2560719) | Cod sursa (job #380426) | Cod sursa (job #38773) | Cod sursa (job #2722873) | Cod sursa (job #1931976)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,incadrari=0,gasit;
string sir1,sir2;
vector <int> pozitii(1000);
vector <int> sufix(2000000,0);
void calcul_prefix(int &i,int &j)
{
if(sir1[i]==sir1[j])
{
sufix[i]=j+1;
i++;j++;
}
else
{
if(j!=0)
j=sufix[j-1];
else
{
sufix[i]=0;
i++;
}
}
if(i<n)
calcul_prefix(i,j);
}
void gasire_sir()
{
int i=0;
for(int j=0;j<m;j++)
{
while(i>0&&sir1[i]!=sir2[j])
i=sufix[i];
if(sir1[i]==sir2[j])
i++;
if(i==n)
{
if(incadrari<1000)
pozitii[incadrari]=j-i+1;
incadrari++;
i=sufix[i-1];
}
}
}
void KMP()
{
int i=1,j=0;
calcul_prefix(i,j);
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();
}