Pagini recente » Cod sursa (job #3232669) | Cod sursa (job #2161156) | Cod sursa (job #1097947) | Cod sursa (job #1029783) | Cod sursa (job #631031)
Cod sursa(job #631031)
#include<stdio.h>
#include<string.h>
#include<vector>
#define nmax 2000003
#define min(a,b) a>b? b:a
using namespace std;
//vector <int> sol;
char a[nmax],b[nmax];
int p[nmax],sol[1000];
void kmp_prefix(char *a,int n){
int k=-1;
p[0]=-1;
for(int i=1;i<n;++i){
while(k>=0 && a[k+1]!=a[i])
k=p[k];
if(a[k+1]==a[i])
++k;
p[i]=k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
//scanf("%s",&a);
//scanf("%s",&b);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
int n=0,m=0;
while((a[n]>='0' && a[n]<='9') || (a[n]>='a' && a[n]<='z') || (a[n]>='A' && a[n]<='Z'))
++n;
while((b[m]>='0' && b[m]<='9') || (b[m]>='a' && b[m]<='z') || (b[m]>='A' && b[m]<='Z'))
++m;
kmp_prefix(a,n);
int k=-1;
int j=0,nr=0;
for(int i=0;i<m;i++){
while(k>=0 && a[k+1]!=b[i])
k=p[k];
if(a[k+1]==b[i])
++k;
if(k==n-1){
++nr;
if(nr<=1000)
sol[nr-1]=i-n+1;
}
}
printf("%d\n",nr);
k=min(nr,1000);
for(j=0;j<k;j++)
printf("%d ",sol[j]);
return 0;
}