Pagini recente » Cod sursa (job #1913528) | Cod sursa (job #867449) | Rating Lupu Mihnea (Mihnea1404) | Istoria paginii utilizator/lazarlivia | Cod sursa (job #1819157)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define BUF_SIZE 1<<17
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
if(pbuf==BUF_SIZE){
fread(buf, BUF_SIZE, 1, fi);
pbuf=0;
}
return buf[pbuf++];
}
inline long long nextnum(){
long long a=0;
char c=nextch();
while((c<'0' || c>'9') && c!='-')
c=nextch();
int semn=1;
if(c=='-'){
semn=-1;
c=nextch();
}
while('0'<=c && c<='9'){
a=a*10+c-'0';
c=nextch();
}
return a*semn;
}
#define MAXN 2000000
int n, m;
char N[1+2*MAXN];
int Z[1+2*MAXN];
int st[1+MAXN], last=0;
int main(){
fi=fopen("strmatch.in","r");
fo=fopen("strmatch.out","w");
char c=nextch();
while(c!='\n'){
N[++n]=c;
c=nextch();
}
m=n;
c=nextch();
while(c!='\n'){
N[++n]=c;
c=nextch();
}
int L=1, R=1;
for(int k=2;k<=n;k++){
if(k>R){
int i=1, j=k;
while(j<=n && N[i]==N[j]){i++;j++;}
i--;j--;
L=k;R=j;
Z[k]=R-L+1;
}
else{
int k2=k-L+1;
if(Z[k2]<R-k+1)
Z[k]=Z[k2];
else{
//printf("Da ");
int i=R-k+2, j=R+1;
//printf("%d %d\n", i, j);
while(j<=n && N[i]==N[j]){i++;j++;}
i--;j--;
L=k;R=j;
Z[k]=j-k+1;
}
}
//printf("%d\n", Z[k]);
if(k>m && Z[k]>=m)
st[++last]=k-m-1;
}
fprintf(fo,"%d\n", last);
for(int i=1;i<=last;i++)
fprintf(fo,"%d ", st[i]);
fclose(fi);
fclose(fo);
return 0;
}