Cod sursa(job #2216884)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 28 iunie 2018 12:04:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define NMAX 2000005

int match[NMAX], z[NMAX], n, m, ans, answers[NMAX];
char p[NMAX], s[NMAX];

void PreprocesarePi() {
    int i, stanga = 0, dreapta = 0, poz, nr;
    for(i = 2; i <= m; i++) {
        if(i > dreapta) {
            poz = 1;
            while(i + poz - 1 <= m && p[poz] == p[i + poz - 1])
                poz++;
            poz--; z[i] = poz;
            if(poz) {
                dreapta = i + poz - 1;
                stanga = i;
            }
            continue;
        }
        nr = i - stanga + 1;
        if(i + z[nr] - 1 < dreapta)
            z[i] = z[nr];
        else {
            z[i] = dreapta - i + 1;
            stanga = i;
            while(dreapta < m && p[z[i] + 1] == p[dreapta + 1]) {
                z[i]++;
                dreapta++;
            }
        }
    }
}

void solve() {
    int i, stanga = 0, dreapta = 0, poz, nr;
    memset(match, 0, sizeof(match));
    for(i = 1; i <= n; i++) {
        if(i > dreapta) {
            poz = 1;
            while(poz <= m && i + poz - 1 <= n && p[poz] == s[i + poz - 1])
                poz++;
            poz--; match[i] = poz;
            if(poz) {
                dreapta = i + poz - 1;
                stanga = i;
            }
            if(match[i] == m) {
                answers[++ans] = i;
            }
            continue;
        }
        nr = i - stanga + 1;
        if(i + z[nr] - 1 < dreapta)
            match[i] = z[nr];
        else {
            match[i] = dreapta - i + 1;
            stanga = i;
            while(match[i] < m && dreapta < n && p[match[i] + 1] == s[dreapta + 1]) {
                match[i]++;
                dreapta++;
            }
        }
        if(match[i] == m) {
            answers[++ans] = i;
        }
    }
}

int main () {
    int aux,i,p1,p2;

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s", p + 1); m = strlen(p + 1);
    scanf("%s", s + 1); n = strlen(s + 1);

    PreprocesarePi();
    solve();

    printf("%d\n", ans);
    if(ans > 1000) {
        ans = 1000;
    }
    for(int i = 1; i <= ans; i++) {
        printf("%d ", answers[i] - 1);
    }
    printf("\n");

    return 0;
}