Pagini recente » Cod sursa (job #2436965) | Cod sursa (job #2372925) | Cod sursa (job #2402424) | Cod sursa (job #1182398) | Cod sursa (job #2405715)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmath.out");
#define minim(a, b) ((a < b) ? a : b)
#define sirMax 2000001
int lungimeA, lungimeB;
char sirA[sirMax], sirB[sirMax];
int pi[sirMax], pos[1024];
void make_prefix(){ //Calcul functie prefix
int i, q = 0;
pi[1] = 0;
for(i = 2; i <= lungimeA; ++i){
while(q > 0 && sirA[q+1] != sirA[i])
q = pi[q];
if(sirA[q+1] == sirA[i])
++q;
pi[i] = q;
}
}
void KMP(int &nr){ //Algoritm potrivire KMP
int q = 0;
nr = 0;
for(int i = 1; i <= lungimeB; ++i){
while(q > 0 && sirA[q+1] != sirB[i])
q = pi[q];
if(sirA[q+1] == sirB[i])
++q;
if(q == lungimeA){
q = pi[lungimeA];
++nr;
if(nr <= 1000)
pos[nr] = i - lungimeA;
}
}
}
int main()
{
//Citire
sirA[0] = ' ';
sirB[0] = ' ';
fin.get(sirA + 1, sirMax);
fin.get();
fin.get(sirB + 1, sirMax);
lungimeA = strlen(sirA) - 1;
lungimeB = strlen(sirB) - 1;
//Rezolvare problema
int nr = 0; //Numarul de aparitii ale sirului A in sirul B;
make_prefix();
KMP(nr);
//Afisare
fout << nr << "\n";
for(int i = 1; i <= minim(nr, 1000); ++i)
fout << pos[i] << " ";
fin.close();
fout.close();
return 0;
}