Cod sursa(job #2791189)

Utilizator teomarsTeodora Sintea teomars Data 30 octombrie 2021 10:46:02
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char a[2000005], b[2000005];
int l1, l2, sol[1005], p[2000005], nr;

void citire()
{
    scanf("%s\n %s", a, b);
    l1 = strlen(a);
    l2 = strlen(b);
}

void prefix(){
    int j = -1;
    p[0]=-1;
    for(int i = 0; i < l1; i++){
        while(j >= 0 && a[i] != a[j])
            j = p[j];
        j++;
        p[i+1]=j;
    }
}

void KMP(){
    int j = 0;
    for(int i = 0; i < l2; i++){
        while(j >= 0 && b[i] != a[j])
            j = p[j];
        j++;
        if(j == l1){
            j = p[j];
            sol[nr++] = i+1-l1;
        }
    }
}

void afisare(){
    printf("%d\n", nr);
    int mini = min(nr, 1000);
    for(int i = 0; i < mini; i++)
        printf("%d ", sol[i]);
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    citire();
    prefix();
    KMP();
    afisare();
    return 0;
}