Pagini recente » Cod sursa (job #1836227) | pt_round12 | Cod sursa (job #2786762) | Cod sursa (job #674608) | Cod sursa (job #662481)
Cod sursa(job #662481)
#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(){
//scanf("%s", P);//citesc modelul ~pattern~
//scanf("%s", T);//citesc textul in care caut aparitiile
gets(P);
gets(T);
m = strlen( P );
n = strlen( T );
--m; --n;
//printf("%s\n", P);
//printf("%s", T);
}
void urmatorul(){
urm[0] = 0;
int k = -1;
for(int q=1; q<=m; ++q){//determin cel mai mare prefix din P care e sufix pentru sirul P[1..q]
while( k>-1 && P[k+1] != P[q]) k = urm[k];
if (P[k+1] == P[q]) ++k;
urm[q] = k;
}
}
void rezolva(){
int k=-1;
urmatorul();
for(int q=0; q<=n; ++q){
while( k>-1 && P[k+1] != T[q]) k = urm[k];
if (P[k+1] == T[q]) ++k;
if (k == m){
Sol[ ++Sol[0] ] = q-m;
k = urm[k];
}
}
}
void scrie(){
printf("%d\n", Sol[0]);
for(int i=1; i<=Sol[0]; ++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;
}