Pagini recente » Cod sursa (job #1437612) | Cod sursa (job #1513955) | Cod sursa (job #1027535) | Cod sursa (job #1298811) | Cod sursa (job #1201937)
#include<cstdio>
const int N=2000000,MAX_OUTPUT=1000;
int prefix[N+1],res[N+1];
char s1[N+1],s2[N+1];
FILE*in,*out;
int n1,n2,noRes;
void scan(){
fscanf(in,"%s\n",s2);
fscanf(in,"%s",s1);
}
int stringLenght(char s[N+1]){
int i=0;
while(s[i]!='\0')
i++;
return i;
}
void shift(){
int i;
for(i=n1;i>=1;i--)
s1[i]=s1[i-1];
for(i=n2;i>=1;i--)
s2[i]=s2[i-1];
}
void init(){
in=fopen("strmatch.in","r");
out=fopen("strmatch.out","w");
scan();
n1=stringLenght(s1);
n2=stringLenght(s2);
shift();
}
void setPrefix(){
int i,k=0;
prefix[1]=0;
for(i=2;i<=n2;i++){
while(k>0&&s2[i]!=s2[k+1])
k=prefix[k];
if(s2[i]==s2[k+1])
k++;
prefix[i]=k;
}
}
int min2(int a,int b){
if(a<b)
return a;
return b;
}
void print(){
int i;
fprintf(out,"%d\n",noRes);
noRes=min2(noRes,MAX_OUTPUT);
for(i=1;i<=noRes;i++)
fprintf(out,"%d ",res[i]-1);
}
void solve(){
int i,k=0;
setPrefix();
for(i=1;i<=n1;i++){
while(k>0&&s1[i]!=s2[k+1])
k=prefix[k];
if(s1[i]==s2[k+1])
k++;
if(k==n2){
res[++noRes]=i-n2+1;
k=prefix[k];
}
}
print();
}
void closeFiles(){
fclose(in);
fclose(out);
}
int main(){
init();
solve();
closeFiles();
return 0;
}