Pagini recente » Cod sursa (job #2101299) | Cod sursa (job #232070) | Cod sursa (job #3283810) | Cod sursa (job #2268467) | Cod sursa (job #407222)
Cod sursa(job #407222)
#include <stdio.h>
#include <algorithm>
#define MAXX 2000005
using namespace std;
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
char P[MAXX],T[MAXX];
int urm[MAXX],pos[1005];
int p,t,k,q,n;
void citire(){
/*do{
fscanf(f,"%c",&P[++p]);
}while(P[p]!='\n');
P[p]=0;
p--;
do{
fscanf(f,"%c",&T[++t]);
if(feof(f)){
t--;
break;
}
}while(T[t]!='\n');
if(T[t]=='\n'){
T[t]=0;
t--;
}*/
fscanf(f,"%s %s",P,T);
p=strlen(P);
t=strlen(T);
int i;
for(i=p;i>=0;i--) P[i+1]=P[i];
for(i=t;i>=0;i--) T[i+1]=T[i];
}
void urmatorul(){
int i;
k=0;
for(i=2;i<=p;i++){
while(k>0 && P[k+1]!=P[i]){
k=urm[k];
}
if(P[k+1]==P[i]){
k++;
}
urm[i]=k;
}
}
void solve(){
urmatorul();
int i;
k=0;
for(i=1;i<=t;i++){
while(k>0 && P[k+1]!=T[i]){
k=urm[k];
}
if(P[k+1]==T[i]){
k++;
}
if(k==p){
k=urm[k];
n++;
if(n<=1000)
pos[n]=i-p;
}
}
}
void afis(){
int i;
fprintf(g,"%d\n",n);
n=min(n,1000);
for(i=1;i<=n;i++){
fprintf(g,"%d ",pos[i]);
}
}
int main(){
citire();
solve();
afis();
fclose(f);
fclose(g);
return 0;
}