#include <stdio.h>
#include <string.h>
#include <dirent.h>
#include <sys/types.h>
#include <regex.h>
#include <stdlib.h>

typedef struct catalog_of_letters{
    char name;
    char* path;
}catalog_of_letters;

void getStruct(catalog_of_letters** catalog, char* path, int count){
    catalog[count]->name = ptr[strlen(path)-5];
    catalog[count]->path = strdup(path);
}

int cmp(const void* a, const void* b){
    return (*(catalog_of_letters**)a)->name - (*(catalog_of_letters**)b)->name;
}

int bsearch_cmp(const void* a, const void* b){
    return *(char*)a - (*(catalog_of_letters**)b)->name;
}

int isValid(char *filName){
    char *regexp = "^[a-zA-z].txt$";
    regex_t regexComp;

    if(regcomp(&regexComp, regexp, REG_EXTENDED)){
        return 0;
    }

    return regexec(&regexComp, fileName, 0, NULL, 0) == 0;
}

void depthFirstSearch(char *startDir, catalog_of_letters** catalog, int* count){
    char nextDir[200] = {0};
    strcpy(nextDir, startDir);

    DIR *dir = opendir(startDir);

    if(!dir) {
        return;
    }

    struct dirent *dirEntity = readdir(dir);
    while(dirEntity){

        if((dirEntity->d_type == DT_DIR) &&
            (strcmp(dirEntity->d_name, ".") != 0) &&
            (strcmp(dirEntity->d_name, "..") != 0)) {
                strcat(nextDir, "/");
                strcat(nextDir, dirEntity->d_name);
                depthFirstSearch(nextDir, catalog, count);
                nextDir[strlen(nextDir)] = '\0';
        }

        if((dirEntity->d_type == DT_REG) && isValid(dirEntity->d_name)) {
            strcat(nextDir, "/");
            strcat(nextDir, dirEntity->d_name);
            getStruct(catalog, nextDir, *count)
            nextDir[strlen(nextDir)] = '\0';
            *count++;
        }

        dirEntity = readdir(dir);
    }

    closedir(dir);
}

void printDirPathsEqWordFrag(
    catalog_of_letters** catalog,
    char* word,
    int index,
    int count,
    FILE *f
){
    if(index > strlen(word)-1) {
        return;
    }

    catalog_of_letters** catalogBinarySearch;

    catalogBinarySearch = bsearch(
        &word[index],
        catalog,
        count,
        sizeof(struct catalog_of_letters*),bsearch_cmp
    );

    if(catalogBinarySearch){
        fputs((*catalogBinarySearch)->path, f);
        fputs("\n", f);
        (*catalogBinarySearch)->path[0] = '\0';
    }

    printDirPathsEqWordFrag(catalog, word, index + 1, count, f);
}


int main(){
    FILE *f = fopen("result.txt", "w");
    char word[100];
    fgets(word,100,stdin);
    word[strlen(word)-1]='\0';
    catalog_of_letters** catalog = (catalog_of_letters**)malloc(66*sizeof(catalog_of_letters*));
    int i;
    for(i =0;i<66;i++)
        catalog[i] = calloc(1,sizeof(catalog));

    int countOfLevels = 0;
    depthFirstSearch("./tmp", catalog, &countOfLevels)
    qsort(catalog, countOfLevels, sizeof(catalog_of_letters*), cmp);
    printDirPathsEqWordFrag(catalog, word, 0, countOfLevels, f);

    return 0;
}