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

FILE *f;
size_t  lengthOfTemplate = 0,
lengthOfBuffer = 0;

void getLine(char* dst, bool isTemplate) {
    char currentSymbol;
    size_t currentLength = 0;
    while ((currentSymbol = (char)getchar()) != '\n') {
        dst[currentLength++] = currentSymbol;

        if (!isTemplate && currentLength == lengthOfTemplate) {
            lengthOfBuffer = lengthOfTemplate;
            return;
        }
    }

    if (isTemplate) {
        lengthOfTemplate = currentLength;
    }
    else {
        lengthOfBuffer = currentLength;
    }
}

void getMoves(size_t* moves, char* pattern) {
    for (size_t i = lengthOfTemplate - 2; i > 0; i--) {
        if (moves[(int)pattern[i]] == lengthOfTemplate) {
            moves[(int)pattern[i]] = lengthOfTemplate - i - 1;
        }
    }
    if (moves[(int)pattern[0]] == lengthOfTemplate) {
        moves[(int)pattern[0]] = lengthOfTemplate - 1;
    }
}
size_t getCurrentMove(char* pattern, char* buffer, size_t* moves, size_t currentIndex) {
    for (size_t i = lengthOfTemplate - 1; i > 0; i--) {
        printf("%zu ", currentIndex--);
        if (buffer[i] != pattern[i]) {
            return moves[(int)buffer[lengthOfTemplate - 1]];
        }
    }
    printf("%zu ", currentIndex);
    if (buffer[0] != pattern[0]) {
        return moves[(int)pattern[0]];
    }
    else    return lengthOfTemplate;
}

void startAlgorithm(char* pattern, char* buffer, size_t* moves) {
    size_t currentIndex = lengthOfTemplate;

    while (1) {
        size_t currentMove = getCurrentMove(pattern, buffer, moves, currentIndex);

        if (currentMove == lengthOfTemplate) {
            for (size_t i = 0; i < lengthOfTemplate; i++) {
                currentIndex++;
                if (buffer[i] = (char)getchar()) {
                    if (buffer[i] != '\n') {
                        continue;
                    }
                    else {
                        free(pattern);
                        free(buffer);
                        system("pause");
                        exit(0);
                    }
                }
                else {
                    free(pattern);
                    free(buffer);
                    system("pause");
                    exit(0);
                }
            }
        }
        else {
            memcpy(buffer, buffer + currentMove, lengthOfTemplate - currentMove);
            for (size_t i = lengthOfTemplate - currentMove; i < lengthOfTemplate; i++) {
                currentIndex++;
                if (buffer[i] = (char)getchar()) {
                    if (buffer[i] != '\n') {
                        continue;
                    }
                    else {
                        free(pattern);
                        free(buffer);
                        system("pause");
                        exit(0);
                    }
                }
                else {
                    free(pattern);
                    free(buffer);
                    exit(0);
                }
            }
        }
    }
}

int main() {
    char* pattern = (char*)calloc(17, sizeof(char));
    if (!pattern) {
        printf("No memory");
        system("pause");
        return 0;
    }
    else {
        getLine(pattern, true);
        if (lengthOfTemplate == 0) {
            printf("bad input");
            free(pattern);
            system("pause");
            return 0;
        }
    }

    char* buffer = (char*)calloc(lengthOfTemplate + 1, sizeof(char));
    if (!pattern) {
        printf("No memory");
        system("pause");
        return 0;
    }
    else {
        getLine(buffer, false);
        if (lengthOfBuffer < lengthOfTemplate) {
            free(pattern);
            free(buffer);
            system("pause");
            return 0;
        }
    }

    size_t moves[256];
    for (size_t i = 0; i < 256; i++) {
        moves[i] = lengthOfTemplate;
    }
    getMoves(moves, pattern);

    startAlgorithm(pattern, buffer, moves);

    system("pause");
    return 0;
}