Pagini recente » Cod sursa (job #1600192) | Cod sursa (job #1083031) | Cod sursa (job #73787) | Cod sursa (job #72432) | Cod sursa (job #662546)
Cod sursa(job #662546)
#include <cstdio>
#include <cstring>
#define Nmax 2000005
using namespace std;
char P[Nmax], T[Nmax];
int n, m, urm[Nmax];
int Sol[Nmax];
void citeste(){
//sirurile sunt indexate de la 1 la length( P )/( T ) +1
scanf("%s", P+1);//citesc modelul ~pattern~
scanf("%s", T+1);//citesc textul in care caut aparitiile
m = strlen( P+1 );
n = strlen( T+1 );
}
void urmatorul(){
urm[1] = 0;
int q = 0;
for(int i=2; i<=m; ++i){//determin cel mai mare prefix din P care e sufix pentru sirul P[1..q]
while( q>0 && P[q+1] != P[i]) q = urm[q];//cat timp nu gasesc un sir pe care sa`l pot continua ma duc mai departe
if (P[q+1] == P[i]) ++q;//daca urmatoare potrivire e corecta o continui
urm[i] = q;//salvez lungimea
}
}
void rezolva(){
int q=0;
urmatorul();
for(int i=1; i<=n; ++i){
while( q>0 && P[q+1] != T[i]) q = urm[q];//cat timp nu se potrivesc pozitiile P[q+1] , T[i] sar la urmatoare pozitie
if (P[q+1] == T[i]) ++q;//daca urmatoarea potrivire e corecta o continui
if (q == m){//daca am gasit o aparitie o salvez
Sol[ ++Sol[0] ] = i-m;
q = urm[q];//sar la urmatoarea pozitie
}
}
}
void scrie(){
//afisez doar primele 1000 aparitii
if (Sol[0] > 1000) Sol[0] = 1000;
printf("%d\n", 1000);
for(int i=1; i<=1000; ++i)
printf("%d ",Sol[i]);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citeste();
rezolva();
scrie();
fclose(stdin);
fclose(stdout);
return 0;
}