gistfile1.txt

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

typedef struct str_pos {
    ssize_t letter_pos;
    ssize_t word_pos;
} str_pos;

typedef struct array {
    str_pos *ptr;
    size_t len;
} array;

typedef struct string {
    char *str;
    size_t len;
} string;

array* matrix_generate(array * positions, string line, string abbr) {
    for (size_t i = 0; i < 26; i++) {
        positions[i].ptr = malloc(sizeof(str_pos) * line.len);
        positions[i].len = 0;
    }
    ssize_t i = 0;
    ssize_t current_word = -1;
    char ch = toupper(line.str[i]);
    while(isspace(ch) && ch != '\0') {
        i++;
        ch = toupper(line.str[i]);
    }
    current_word++;
    while(ch != '\0') {
        if (isspace(ch)) {
            while(isspace(ch) && ch != '\0') {
                i++;
                ch = toupper(line.str[i]);
            }
            current_word++;
        }
        if (strchr(abbr.str, ch)) {
            positions[ch - 'A'].ptr[positions[ch - 'A'].len].letter_pos = i;
            positions[ch - 'A'].ptr[positions[ch - 'A'].len].word_pos = current_word;
            positions[ch - 'A'].len++;
        }
        i++;
        ch = toupper(line.str[i]);
    }
}

bool isAvailable(str_pos current_pos, str_pos previous_pos, ssize_t current_letter, ssize_t max_letter) {
    return ((current_pos.word_pos > previous_pos.word_pos) ||
            (current_pos.word_pos == previous_pos.word_pos && current_pos.letter_pos > previous_pos.letter_pos &&
             current_letter < max_letter));
}

size_t count_greater_than(
        array arr,
        str_pos pos,
        ssize_t current_letter_in_word,
        ssize_t max_letter_in_word
        ) {
    for (size_t i = 0; i < arr.len; ++i) {
        if (arr.ptr[i].letter_pos > pos.letter_pos) {
            if (isAvailable(arr.ptr[i], pos, current_letter_in_word, max_letter_in_word)) {
                return arr.len - i;
            }
        }
    }
    return 0;
}


size_t find_all_comb(
        array *positions,
        string abbr,
        ssize_t curr_abbr_pos,
        str_pos prev_str_pos,
        ssize_t current_letter_in_word,
        ssize_t max_letter_in_word
        ) {
    array column = positions[abbr.str[curr_abbr_pos] - 'A'];
    if (curr_abbr_pos >= abbr.len - 1) {
        return count_greater_than(
                column,
                prev_str_pos,
                current_letter_in_word + 1,
                max_letter_in_word
                );
    } else {
        size_t sum = 0;
        size_t comb = 0;
        for (size_t i = 0; i < column.len; ++i) {
            if (isAvailable(column.ptr[i], prev_str_pos, current_letter_in_word + 1, max_letter_in_word)) {
                comb = find_all_comb(
                        positions,
                        abbr,
                        curr_abbr_pos + 1,
                        column.ptr[i],
                        column.ptr[i].word_pos == prev_str_pos.word_pos ? current_letter_in_word + 1 : 0,
                        max_letter_in_word
                        );
                if (comb > 0) {
                    sum += comb;
                } else {
                    return sum;
                }
            }
        }
        return sum;
    }
}

int main()
{
    char *_abbr = "DXDML";
    char *_line = "DXDML DXDML DXDML DXDML DXDML DXDML DXDML DXDML DXDML DXDML DXDML DXDML";
    size_t max_letter_in_word = 7;
    array positions[26];
    string line = (string){_line, strlen(_line) };
    string abbr = (string){_abbr, strlen(_abbr) };
    matrix_generate(positions, line, abbr);
    str_pos start_pos = (str_pos){-1, 0};
    size_t comb_num = find_all_comb(
            positions,
            abbr,
            0,
            start_pos,
            -1,
            max_letter_in_word);
    printf("%lu\n", comb_num);
    return 0;
}