Pagini recente » Cod sursa (job #1815829) | Cod sursa (job #1937185) | Cod sursa (job #2405285) | Atasamentele paginii Clasament preoji2014_3_11_12 | Cod sursa (job #2405726)
#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);
fin.getline(sirA + 1, sirMax);
fin.getline(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;
}