Pagini recente » Cod sursa (job #6670) | Arhiva de probleme | Cod sursa (job #1128839) | Cod sursa (job #2816961) | Cod sursa (job #143969)
Cod sursa(job #143969)
#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,MAX_N+2,stdin);
fgets(t,MAX_N+2,stdin);
for (; (t[lng]>='A' && t[lng]<='Z') || (t[lng]>='a' && t[lng]<='z')
||(t[lng]>='0' && t[lng]<='9');lng++);
for (; (p[len]>='A' && p[len]<='Z')||(p[len]>='a' && p[len]<='z')
||(p[len]>='0' && p[len]<='9');len++);
for (int i=lng;i;--i){t[i]=t[i-1];}
for (int i=len;i;--i){p[i]=p[i-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){
++nrsol;
if (nrsol<=1000){
sol[nrsol]=i-len;
}
q=fpi[q];
}
}
}
void solve(void){
int i;
printf("%d\n",nrsol);
for (i=1;i<min(nrsol,1000);i++){
printf("%d ",sol[i]);}
if (nrsol){printf("%d\n",sol[min(nrsol,1000)]);}
fclose(stdout);
}
int main(void){
iofile();
calcul_pi();
kmp_match();
solve();
return 0;
}