Pagini recente » Cod sursa (job #1952557) | Cod sursa (job #1630732) | Cod sursa (job #1332584) | Cod sursa (job #1520960) | Cod sursa (job #2344401)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int ap[1001], k;
void getZarr(string str, int Z[]);
void search(string text, string pattern, int &matches)
{
//concateneaza pat cu txt
string concat=pattern+"$"+text;
int l=concat.length();
//construieste vectorul Z
int Z[l];
getZarr(concat, Z);
//verificam match-urile
for(int i=0; i<l; ++i)
{
//daca z[i] == lungimea pat am gasit un match
if(Z[i]==pattern.length())
{
matches++;
if(k<1000)
ap[k++]=i-pattern.length()-1;
}
}
}
//Construieste Z
void getZarr(string str, int Z[])
{
int n=str.length();
int L, R, k;
L=R=0;
for(int i=1; i<n; ++i)
{
// if i>R nimic nu se "match-uieste"
if(i>R)
{
L=R=i;
while(R<n && str[R-L]==str[R])
R++;
Z[i]=R-L;
R--;
}
else
{
k=i-L;
if(Z[k]<R-i+1)
Z[i]=Z[k];
else
{
L=i;
while(R<n && str[R-L]==str[R])
R++;
Z[i]=R-L;
R--;
}
}
}
}
int main()
{
int matches=0;
string pat, text;
getline(f, pat);
getline(f, text);
search(text, pat, matches);
g<<matches<<'\n';
if(k!=0)
for(int i=0; i<k; ++i)
g<<ap[i]<<' ';
return 0;
}