Cod sursa(job #2791154)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 30 octombrie 2021 10:11:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <cstring>

using namespace std;

const int NMAX = 2000010;

int micl, marel, lps[NMAX + 1], ans[1010], ansl;
char mare[NMAX + 1], mic[NMAX + 1];

void generLps() {
    lps[0] = -1;
    for(int i = 0, j = -1; i < micl;) {
        while(j >= 0 && mic[i] != mic[j])
            j = lps[j];
        lps[++i] = ++j;
    }
}

void kmp() {
    for(int i = 0, j = 0; i < marel;) {
        while(j >= 0 && mare[i] != mic[j])
            j = lps[j];
        ++i, ++j;
        if(j == micl) {
            j = lps[j];
            if(++ansl <= 1000)
                ans[ansl] = i - micl;
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", mic, mare);
    micl = strlen(mic), marel = strlen(mare);
    generLps();
    kmp();
    printf("%d\n", ansl);
    ansl = min(ansl, 1000);
    for(int i = 1; i <= ansl; ++i)
        printf("%d ", ans[i]);
    return 0;
}