Pagini recente » Cod sursa (job #233379) | Cod sursa (job #1961182) | Cod sursa (job #2213980) | Cod sursa (job #126432) | Cod sursa (job #1813738)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#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 pi[1+MAXN];
int N[1+MAXN], M[1+MAXN];
int n, m;
inline int getPi(){
pi[1]=0;
int k=0;
for(int i=2;i<=n;i++){
while(k>0 && N[k+1]!=N[i])
k=pi[k];
if(N[k+1]==N[i])
k++;
pi[i]=k;
}
}
int st[1+MAXN], ind=0;
int main(){
fi=fopen("strmatch.in","r");
fo=fopen("strmatch.out","w");
char c=nextch();
while(c!='\n' && c!=EOF){
N[++n]=c;
c=nextch();
}
c=nextch();
while(c!='\n' && c!=EOF){
M[++m]=c;
c=nextch();
}
getPi();
int q=0;
for(int i=1;i<=m;i++){
while(q>0 && N[q+1]!=M[i])
q=pi[q];
if(N[q+1]==M[i])
q++;
if(q==n)
st[ind++]=i;
}
fprintf(fo,"%d\n", ind);
for(int i=0;i<ind;i++)
fprintf(fo,"%d ", st[i]-n);
fclose(fi);
fclose(fo);
return 0;
}