Pagini recente » Cod sursa (job #1988451) | Cod sursa (job #2656882) | Cod sursa (job #429011) | Cod sursa (job #3165453) | Cod sursa (job #728685)
Cod sursa(job #728685)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int Urm[2000001];
char T[2000001]; // textul
char P[2000001]; // patternu'
int n, m, NrSol, SOL[2000001];
void Urmatorul()
{
int k=-1, x;
Urm[0]=0;
for(x=1;x<m;x++)
{
while (k>0 && P[k+1]!=P[x])
k=Urm[k];
if (P[k+1]==P[x])
k++;
Urm[x]=k;
}
}
int main()
{
int i, x=-1;
f.getline(P, 2000001); f.getline(T, 2000001);
n=strlen(T); m=strlen(P);
Urmatorul(); // am facut functia prefix
for (i=0; i<n; i++)
{
while (x>0 && P[x+1]!=T[i])
x=Urm[x];
if (P[x+1]==T[i]) // am mai gasit un caracter corect
x++;
if (x==m-1)
{
SOL[++NrSol]=i-x;
x=Urm[x];
}
}
g<<NrSol<<'\n';
for(i=1;i<=NrSol;i++)
g<<SOL[i]<<" ";
f.close();
g.close();
return 0;
}