Pagini recente » Cod sursa (job #495601) | Cod sursa (job #2818799) | Borderou de evaluare (job #2979244) | Cod sursa (job #3226394) | Cod sursa (job #695022)
Cod sursa(job #695022)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
#define NMAX 2000002
/**
* Algoritmul Knuth-Morris-Pratt (KMP)
* Potrivirea sirurilor
*/
#define MAXR 1000
vector<int> R;
int nrR;
int Urm[NMAX];
char T[NMAX], P[NMAX];
int N, M;
void citire();
void urmatorul();
void afisare();
int main()
{
R.reserve(MAXR);
int x = -1;
citire();
urmatorul();
for(int i=0; i<N; i++)
{
while(x > 0 && P[x+1] != T[i])
x = Urm[x];
if(P[x+1] == T[i])
x++; // s-au potrivit
if(x == M-1) {
x = Urm[x];
nrR++;
R.push_back(i-M+1);
}
}
afisare();
}
void urmatorul()
{
int k = -1;
Urm[0] = 0;
for(int 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;
}
}
void citire()
{
ifstream fin("strmatch.in");
fin.getline(P, NMAX);
fin.getline(T, NMAX);
N = strlen(T);
M = strlen(P);
fin.close();
}
void afisare()
{
ofstream fout("strmatch.out");
fout<<nrR<<'\n';
int i = 0;
vector<int> :: iterator it;
for(it = R.begin(); it != R.end(); it++) {
fout<<*it<<' ';
i++;
if(i > NMAX && N > NMAX)
break;
}
fout.close();
}