Cod sursa(job #2469733)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 7 octombrie 2019 21:54:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
//
//  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;
}