Pagini recente » Cod sursa (job #2148523) | Cod sursa (job #870986) | Cod sursa (job #2613365) | Cod sursa (job #1131803) | Cod sursa (job #1142200)
// Compilare g++ sursa.cpp -o binar
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMax 2000000
//Complexity = O(N+M)
int T[NMax], R[NMax], Na, Nb, aparitii;
char A[NMax], B[NMax];
//A - sirul cautat
//B - sirul in care se cauta aparitiile lui A
void calculT (void) {
int pos, index;
T[0]=-1;
T[1]=0;
pos = 2; //pentru parcurgerea lui T
index = 0; //pentru parcurgerea lui A
while (pos < Na) {
if(A[pos-1]==A[index]) {
++index;
T[pos]=index;
++pos;
} else
if (index>0)
index=T[index];
else {
T[pos]=0;
++pos;
}
}
}
void potrivireSiruri (void) {
int m,i;
i=0;
m=0;
while (m+i<Nb) {
if (B[m+i]==A[i])
if (i==Na-1) {
R[aparitii]=m;
++aparitii;
++m;
i=0;
}
else
++i;
else {
m=m+i-T[i];
if (T[i]>-1)
i = T[i];
else
i = 0;
}
}
}
void printResult (void) {
int i;
printf("%d\n",aparitii);
for (i=0; i<aparitii; ++i)
printf("%d ",R[i]);
}
int main (void) {
int i;
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
Na = strlen(A);
Nb = strlen(B);
aparitii=0;
calculT();
potrivireSiruri();
printResult();
return 0;
}