Pagini recente » Cod sursa (job #171057) | ONIS 2015, Solutii Runda 1 | Cod sursa (job #2149589) | Monitorul de evaluare | Cod sursa (job #143940)
Cod sursa(job #143940)
#include <iostream>
#include <string>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000000
#define MAX_S 1000
using namespace std;
char t[MAX_N+4],p[MAX_N+4];
int fpi[MAX_N+4],len,lng;
int nrsol,sol[MAX_S+1];
void iofile(void){
freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);
fgets(p+1,MAX_N+2,stdin);
fgets(t+1,MAX_N+2,stdin);
lng=strlen(t+1)-1;
len=strlen(p+1)-1;
fclose(stdin);
}
void calcul_pi(void){
int i,q,k;
k=0;
fpi[1]=0;
for (q=2;q<=len;q++){
while (k && p[q]!=p[k+1]){
k=fpi[k];
}
if (p[q]==p[k+1]){k++;}
fpi[q]=k;
}
}
void kmp_match(void){
int q,i;
q=0;
nrsol=0;
for (i=1;i<=lng;i++){
while (q && p[q+1]!=t[i]){
q=fpi[q];
}
if (p[q+1]==t[i]){q++;}
if (q==len){
sol[++nrsol]=i-len;
q=fpi[q];
if (nrsol==1000){return ;}
}
}
}
void solve(void){
int i;
printf("%d\n",nrsol);
for (i=1;i<nrsol;i++){
printf("%d ",sol[i]);}
printf("%d\n",sol[nrsol]);
fclose(stdout);
}
int main(void){
iofile();
calcul_pi();
kmp_match();
solve();
return 0;
}