Pagini recente » Cod sursa (job #124864) | Cod sursa (job #1543456) | Cod sursa (job #3277645) | Cod sursa (job #1443514) | Cod sursa (job #728768)
Cod sursa(job #728768)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, urm[2000001], SOL[2000001], NrSol;
char T[2000001]; // textul
char P[2000001]; // pattern
void functie_prefix()
{
int k=0, i;
urm[1]=0;
for(i=2; i<=m; i++)
{
while(k>0 && P[k+1]!=P[i])
k=urm[k];
if(P[i]==P[k+1])
k++;
urm[i]=k;
}
}
int main()
{
int i, k;
f.getline(P, 2000001); f.getline(T, 2000001);
n=strlen(T); // lungimea textului
m=strlen(P); // lungimea patternului
for(i=n;i>=1;i--)
T[i]=T[i-1];
for(i=m;i>=1;i--)
P[i]=P[i-1];
functie_prefix(); // construiesc functia prefix
k=0;
for(i=1;i<=n;i++)
{
while(k>0 && T[i]!=P[k+1])
k=urm[k];
if(T[i]==P[k+1]) // am gasit inca un caracter corect
k++;
if(k==m) // am gasit solutie
{
SOL[++NrSol]=i-k;
k=urm[k];
}
}
g<<NrSol<<'\n';
for(i=1;i<=NrSol;i++)
g<<SOL[i]<<" ";
g<<'\n';
f.close();
g.close();
return 0;
}