Pagini recente » Cod sursa (job #1981271) | Cod sursa (job #3170080) | Cod sursa (job #2108138) | Cod sursa (job #2483747) | Cod sursa (job #369957)
Cod sursa(job #369957)
using namespace std;
#include <cstdio>
#define MAX 2000010
#define nrLitere (26+26+10)
#define nrPrim 100021
char s[MAX], p[MAX];
int ns,np;
FILE * fin= fopen("strmatch.in","r");
FILE * fout=fopen("strmatch.out","w");
void read();
void KMP();
void write();
int main(){
read();
KMP();
write();
return 0;
}
void read(){
ns=np=0;
fscanf(fin,"%s%s",p,s);
for( ; s[ns] ; ++ns);
for( ; p[np] ; ++np);
}
int nrpoz, nrpp, poz[1010];
void KMP(){
//pregatesc funtia failure
int T[MAX], pos=2, cnd=0;
T[0] = -1, T[1] = 0;
while(pos<=np)
if(p[pos-1] == p[cnd])
T[pos]=cnd+1,pos++,cnd++;
else
if(cnd>0)
cnd = T[cnd];
else
T[pos++] = 0;
//KMP
int m=0,i=0;
while(m+i<ns)
{
// printf("%d %d\n",m,i);
if(p[i] ==s[m+i]){
i++;
if(i==np){
nrpoz++;
if(nrpoz<=1000)
poz[++nrpp] = m;
m = m+i-T[i];
if(i>0) i = T[i];
}
}
else{
m = m+i-T[i];
if(i>0) i = T[i];
}
}
}
void write(){
fprintf(fout,"%d\n",nrpoz);
for(int i=1;i<=nrpp;++i)
fprintf(fout,"%d ",poz[i]);
}