Cod sursa(job #1727417)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 10 iulie 2016 18:50:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <math.h>

#define NMAX 2000005

char str_a[NMAX], str_b[NMAX];
int suffix[NMAX];
int ans[NMAX];

int _min (int a, int b) {

    return a < b ? a : b;

}

int main () {

    int i, j, ans_ind = 0;

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

    scanf ("%s", str_a);
    scanf ("%s", str_b);

    int len_a = strlen(str_a),
        len_b = strlen(str_b);

    j = 0;
    for (i = 1; i < len_a; ++i) {
        while (str_a[i] != str_a[j] && j) {
            j = suffix[j - 1];
        }
        if (str_a[i] == str_a[j])
            ++j;
        suffix[i] = j;
    }
    j = 0;
    /*for (i = 0; i <= len_a; ++i) {
         printf ("%d ", suffix[i]);
    }*/
    for (i = 0; i < len_b; ++i) {
        while (str_b[i] != str_a[j] && j) {
            j = suffix[j - 1];
        }
        if (str_b[i] == str_a[j])
            ++j;
        if (j == len_a) {
            ans[ans_ind++] = i - len_a + 1;
            j = suffix[j - 1];
        }
    }

    int k = _min (ans_ind, 1000);

    printf ("%d\n", ans_ind);
    for (i = 0; i < k; ++i) {
        printf ("%d ", ans[i]);
    }

}