Pagini recente » Cod sursa (job #2901011) | Cod sursa (job #1139510) | Cod sursa (job #1730521) | Cod sursa (job #2138560) | Cod sursa (job #630962)
Cod sursa(job #630962)
#include<stdio.h>
#include<string.h>
#include<vector>
#define nmax 2000003
using namespace std;
vector <int> sol;
char a[nmax],b[nmax];
int p[nmax];
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+1];
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);
int n=strlen(a);
int m=strlen(b);
kmp_prefix(a,n);
int k=-1;
unsigned 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++;
sol.push_back(i-n+1);
}
}
printf("%d\n",nr);
for(j=0;j<sol.size();j++)
printf("%d ",sol[j]);
return 0;
}