Cod sursa(job #2216862)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 28 iunie 2018 10:50:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<string.h>

#define NMAX 2000005

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

int main () {
    int best = 0;

    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);

    for(int i = 2; i <= m; i++) {
        while(best > 0 && p[best + 1] != p[i]) {
            best = pi[best];
        }
        if(p[best + 1] == p[i])
            best++;
        pi[i] = best;
    }

    best = 0;
    for(int i = 1; i <= n && ans < 1000; i++) {
        while(best > 0 && s[i] != p[best + 1])
            best = pi[best];
        if(s[i] == p[best + 1])
            best++;
        if(best == m) {
            answers[++ans] = i - m + 1;
            best = pi[best];
        }
    }

    printf("%d\n", ans);
    for(int i = 1; i <= ans; i++)
        printf("%d ", answers[i] - 1);
    printf("\n");
    return 0;
}