Pagini recente » Cod sursa (job #707983) | Cod sursa (job #83957) | Cod sursa (job #1468856) | Cod sursa (job #286658) | Cod sursa (job #2469733)
//
// main.cpp
// KMP
//
// Created by Darius Buhai on 07/10/2019.
// Copyright © 2019 Darius Buhai. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 2000005
using namespace std;
char A[NMAX], B[NMAX];
int PI[NMAX], pos[1024], M, N;
void create_prefix()
{
int q=0;
PI[1] = 0;
for(int i=2;i<=M;i++){
while(q && A[q+1]!=A[i])
q = PI[q];
if(A[i]==A[q+1])
q++;
PI[i] = q;
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", &*A, &*B);
M = (int)strlen(A);
N = (int)strlen(B);
for(int i=M;i>0;i--) A[i] = A[i-1];
A[0] = ' ';
for(int i=N;i>0;i--) B[i] = B[i-1];
A[0] = ' ';
create_prefix();
int q = 0, n=0;
for(int i=1;i<=N;i++){
while(q && A[q+1]!=B[i])
q = PI[q];
if(B[i]==A[q+1])
q++;
if(q==M){
q = PI[M];
n++;
if(n<=1000)
pos[n] = i-M;
}
}
printf("%d\n", n);
for(int j=1;j<=min(n, 1000);j++)
printf("%d ", pos[j]);
return 0;
}