Cod sursa(job #1726943)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 9 iulie 2016 15:44:39
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.13 kb


#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <math.h>

#define NMAX 2000001

char str_a[NMAX], str_b[NMAX];
int suffix[NMAX];
short 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 != 0) {
            j = suffix[j - 1];
        }
        if (str_a[i] == str_a[j])
            suffix[i] = ++j;
        else 
            suffix[i] = 0;
        ++j;
    }

    j = 0;

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

}