Pagini recente » Cod sursa (job #774060) | Cod sursa (job #1849725) | Cod sursa (job #978966) | Cod sursa (job #2889413) | Cod sursa (job #330883)
Cod sursa(job #330883)
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cstdlib>
using namespace std;
#define MAX 20000200
char A[MAX], B[MAX];
long n,m,i,k,kp[MAX],res[1002],rr;
void build(){
kp[0]=0;
k=0;
for (i=1; i<n; i++){
while (k && A[i]!=A[k]){
k=kp[k];
}
if (A[i]==A[k]){
k++;
}
kp[i]=k;
}
}
void calc(){
k=0;
for (i=0; i<m; i++){
while (k && B[i]!=A[k]){
k=kp[k-1];
}
if (B[i]==A[k]){
k++;
}
if (k==n){
if (res[0]<1000){
res[0]++;
res[res[0]]=i-n+1;
}
else {
rr++;
}
}
}
}
int main(){
freopen("strmatch.in", "r", stdin);
scanf("%s ", &A);
scanf("%s ", &B);
n=strlen(A);
m=strlen(B);
fclose(stdin);
res[0]=0;
rr=0;
build();
calc();
freopen("strmatch.out", "w", stdout);
printf("%ld\n", res[0]+rr);
for (i=1; i<=res[0]; i++){
printf("%ld ", res[i]);
}
fclose(stdout);
return 0;
}