Pagini recente » Cod sursa (job #1825509) | Cod sursa (job #819654) | Cod sursa (job #408629) | Cod sursa (job #824658) | Cod sursa (job #721571)
Cod sursa(job #721571)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
vector<int>p;
char a[2000002],b[2000002];
int u[2000002],n,m,sol=0;
void prefix(){
int i,k=-1;
u[0]=-1;
for(i=1;i<n;i++){
while(k>-1&&a[i]!=a[k+1])k=u[k];
if(a[i]==a[k+1])k++;
u[i]=k; }
}
void kmp(){
int i,k=-1;
for(i=0;i<m;i++){
while(k>-1&&b[i]!=a[k+1])k=u[k];
if(b[i]==a[k+1])k++;
if(k==n-1){ sol++; p.push_back(i-k); k=u[k]; } }
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s ",a);
scanf("%s ",b);
n=strlen(a);
m=strlen(b);
prefix();
kmp();
printf("%d\n",sol);
for(int i=0;i<p.size();i++)printf("%d ",p[i]);
}