Pagini recente » Cod sursa (job #764542) | Cod sursa (job #1384882) | Cod sursa (job #2506196) | Cod sursa (job #2559858) | Cod sursa (job #2520368)
//strmatch infoarena
#include <cstdio>
#include <cstring>
using namespace std;
const int NMAX = 2000003;
char s[NMAX];//string
char w[NMAX];//pattern
int z[NMAX]; //z[i] length of segment starting at position i that is the same as the preffix of the string
int mch=0; //number of matches
bool poz[NMAX]; //poz[i]=1 if there is a match at position i
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",w,s);
int n=strlen(s);
int m=strlen(w);
for(int k=0,st=-1,dr=-1; k<n; ++k){
if(k>dr){
st=dr=k;
while(dr<n && s[dr]==w[dr-st])
++dr;
z[k]=dr-st;
dr--;
}else{
if(k+z[k-st]<=dr)
z[k]=z[k-st];
else{
st=k;
while(dr<n && s[dr]==w[dr-st])
++dr;
z[k]=dr-st;
dr--;
}
}
if(z[k]==m){
++mch;
poz[k]=1;
}
}
/*
for(int k=1,st=0,dr=0; k<l; ++k){
if(k>dr){//if im ahead of current preffix
st=dr=k;
while(dr<l && w[dr]==w[dr-st])
++dr;
z[k]=dr-st;
dr--;
}else{ //if im inside preffix
if(k+z[k-st]<=dr) //checking if preffix goes over boundaries, if it doesn't just copy z
z[k]=z[k-st];
else{ //otherwise we try to expand
st=k;
while(dr<l && w[dr]==w[dr-st])
++dr;
z[k]=dr-st;
dr--;
}
}
}
*/
//display
printf("%d\n",mch);
int cnt=0;
for(int i=0;i<n && cnt<1000;++i)
if(poz[i])
printf("%d ",i),cnt++;
return 0;
}