//ругается валгринд
//Invalid read of size 4
//==12625== at 0x400A90: BMSubst (bmall.c:81) это строчка  k = k + max(deltaone[(int) t[k]], deltatwo[i]);
//==12625== by 0x400B1E: main (bmall.c:89) это строчка     BMSubst(argv[1], argv[2], 123);
//==12625== Address 0x2 is not stack'd, malloc'd or (recently) free'd

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int* suffix(char *s)
{
    int lens = strlen(s);
    int i, t;
    int *sigma = calloc(lens, sizeof(int));
    sigma[lens - 1] = t = lens - 1;
    for (i = lens - 2; i >= 0; i--){
        while ((t < lens - 1) && (s[t] != s[i]))
            t = sigma[t+1];
        if (s[t] == s[i])
            t--;
        sigma[i] = t;
    }
    return sigma;
}

int* delta1(char *s, int size)
{
    int *deltaone = calloc(size, sizeof(int));
    int a;
    int lens = strlen(s);
    for (a = 0; a < size; a++)
        deltaone[a] = lens;
    int j;
    for (j = 0; j < lens; j++)
        deltaone[s[j]] = lens - j - 1;
    return deltaone;
}

int* delta2(char *s)
{
    int lens = strlen(s), i, t;
    int *deltatwo = calloc(lens, sizeof(int));
    int *sigma = suffix(s);
    t = sigma[0];
    for (i = 0; i < lens; i++){
        while (t < i)
            t = sigma[t + 1];
        deltatwo = t - i + lens;
    }
    for (i = 0; i < lens - 1; i++){
        t = i;
        while (t < lens - 1){
            t = sigma[t + 1];
            if (s[i] != s[t])
                deltatwo[t] = lens - i -1;
        }
    }
    free(sigma);
    return deltatwo;
}

void BMSubst(char *s, char *t, int size)
{
    int *deltaone = delta1(s, size);
    int *deltatwo = delta2(s);
    int lens = strlen(s), lent = strlen(t);
    int k, i;
    for (k = lens - 1; k < lent;){
        i = lens - 1;
        while (t[k] == s[i]){
            if (i == 0){
                    printf("%d ", k);
                break;
            }
            i--;
            k--;
        }
        k = k + max(deltaone[(int) t[k]], deltatwo[i]);
    }
    free(deltaone);
    free(deltatwo);
}

int main(int argc, char **argv)
{
    BMSubst(argv[1], argv[2], 123);
    return 0;
}