// STD и стандартные библиотеки
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <iostream>
#include <cstring>
#include <cctype>


struct Word {
    char Text[50];
    unsigned int pos;
    unsigned int line;
};

// Структура списка слов
struct WordList {
    unsigned int count;
    struct Word * Words;
    unsigned int allocated;
};

const int WordLength = 50;                       // Максимальная длина одного слова
const unsigned int RAMLimit = 1000; //2147483648;        // Ограничение по памяти
const double RAMreserv = 15;                    // Сколько RAM зарезервированно (в %)


// Сигнатуры функций
unsigned int GetSubStr(struct WordList * WL);
bool GetTextPrt(struct WordList * WL, unsigned int AvMemory);
void Z_FUC(struct WordList * WL, unsigned int SubStrCount);
void Cutter(struct WordList * WL, unsigned int SubStrCount);

// Координаты
unsigned int x = 1;
unsigned int y = 1;

// Основной цикл
int main() {
    // Переменные
    struct WordList MainStr;
    unsigned int AvMemory = (unsigned int)(RAMLimit * (1-(RAMreserv / 100)));
    unsigned int SubStrCount;
    bool exitkey = true;

    // Инициализация MainStr
    MainStr.count = 0;
    MainStr.Words = (struct Word*)malloc(10*sizeof(struct Word));
    MainStr.allocated = 0;
    // Ввод подстроки + резерв места под уникальное слово
    AvMemory -= GetSubStr(&MainStr);

    // Сохранить длину постоянной части
    SubStrCount = MainStr.count;

    // Считываем и обрабатываем дальнейшие строки
    while (exitkey){
        // Cчитываем допустимый объем
        exitkey = GetTextPrt(&MainStr, AvMemory/2);

        // Включаем Z-функцию и выводим результат
        Z_FUC(&MainStr, SubStrCount);

        // Обрезка строки
        Cutter(&MainStr, SubStrCount);
    }
    system("pause");
}


// Заполнение подстроки
unsigned int GetSubStr(struct WordList * WL) {
    // Переменные
    char Char;
    bool exitkey = false;
    unsigned int i = 0;

    while (!exitkey) {
        // Cчитывание символа
        Char = toupper(getchar());

        // Если нет места
        if (WL->allocated == 0) {
            WL->allocated = (unsigned int)(WL->count * 0.25)+5;
            WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
        }

        // Если символ Буква - добавляем
        if (((Char >= 'A') && (Char <= 'Z')) || ((Char >= '0') && (Char <= '9'))) {
            WL->Words[WL->count].Text[i] = Char;
            i++;
        } else

        // Если символ - пробел
        if (((Char == ' ') || (Char == 't')) && (i > 0)) {
            WL->Words[WL->count].Text[i] = 0;
            WL->allocated--;
            WL->count++;
            i = 0;
        } else

        // Если символ - переход на новую строку
        if (Char == 'n') {
            if (i > 0) {
                WL->Words[WL->count].Text[i] = 0;
                WL->allocated--;
                WL->count++;
                i = 0;
            }
            exitkey = true;
        } else

        // Если это конец ввода
        if (Char == EOF) {
            if (i > 0) {
                WL->Words[WL->count].Text[i] = 0;
                WL->allocated--;
                WL->count++;
                i = 0;
            }
            exitkey = true;
        }
    }

    // Если нет места
    if (WL->allocated == 0) {
        WL->allocated = (unsigned int)(WL->count * 0.25) + 5;
        WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
    }

    // Добавить уникальное слово
    sprintf_s(WL->Words[WL->count].Text, "%s", "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@");
    WL->Words[WL->count].line = 1;
    WL->Words[WL->count].pos = 0;
    WL->allocated--;
    WL->count++;

    return (WL->count * sizeof(struct Word));
}


// Заполнение остальных строк
bool GetTextPrt(struct WordList * WL, unsigned int AvMemory) {
    // Переменные
    char Char;
    bool exitkey = false;
    unsigned int i = 0;

    while (!exitkey){

        // Cчитывание символа
        Char = toupper(getchar());

        // Если нет места
        if (WL->allocated == 0) {
            WL->allocated = (unsigned int)(WL->count * 0.25);
            WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));
        }

        // Доп. определение EOF
        if (Char == '@') Char = EOF;

        // Если символ Буква - добавляем
        if (((Char >= 'A') && (Char <= 'Z')) || ((Char >= '0') && (Char <= '9'))) {
            WL->Words[WL->count].Text[i] = Char;
            i++;
        } else

        // Если доступная память закончилась
        if (AvMemory < (WL->count * sizeof(struct Word))) exitkey = true;

        // Если символ - переход на новую строку
        if (Char == 'n') {
            if (i > 0) {
                WL->Words[WL->count].Text[i] = 0;
                WL->Words[WL->count].line = y;
                WL->Words[WL->count].pos  = x;
                WL->allocated--;
                WL->count++;
                i = 0;
                x = 1;
            }
            y++;
        } else

        // Если символ - пробел
        if (((Char == ' ')|| (Char == 't'))&&(i>0)){
            if (i > 0) {
                WL->Words[WL->count].Text[i] = 0;
                WL->Words[WL->count].pos  = x;
                WL->Words[WL->count].line = y;
                WL->allocated--;
                WL->count++;
            }
            x++;
            i = 0;
        } else

        // Если это конец ввода
        if (Char == EOF){
            if (i > 0) {
                WL->Words[WL->count].Text[i] = 0;
                WL->Words[WL->count].pos  = x;
                WL->Words[WL->count].line = y;
                WL->allocated--;
                WL->count++;
                i = 0;
            }
            exitkey = true;
        }

    }

    return (AvMemory < WL->count * sizeof(struct Word));
}


// Функция минимума (служебная)
unsigned int GetMin(unsigned int l, unsigned int r) {
    if (l <= r) return l; else return r;
}

// Сравнить строки (служебная)
bool smp(const char *str1, const char *str2) {
    return (strcmp(str1, str2) == 0);
}

// Запуск Z функции и вывод результата
void Z_FUC(struct WordList * WL, unsigned int SubStrCount) {
    // Переменные
    unsigned int* DStr;
    unsigned int i; // Тикер для циклов
    unsigned int left = 0; // Необходимо для Z-function
    unsigned int right = 0; // Необходимо для Z-function


    /* Z-функция */

    // Инициализация
    DStr = (unsigned int*)malloc(WL->count*sizeof(unsigned int));
    for (i = 0; i < WL->count; i++) DStr[i] = 0;

    // Работа шайтан машины
    for (i = 1; i < WL->count; ++i) {

        if (i <= right) DStr[i] = GetMin(right - i + 1, DStr[i - left]);

        while (((i + DStr[i]) < WL->count) && (smp(WL->Words[DStr[i]].Text, WL->Words[i + DStr[i]].Text))) {
            ++(DStr[i]);
        }

        if (i + DStr[i] - 1 > right) {
            left = i;
            right = i + DStr[i] - 1;
        }
    }

    // Вывод ответа
    for (i = 0; i < (WL->count - SubStrCount); i++){
        if (DStr[i + SubStrCount] == SubStrCount - 1) {
            printf("%u%s%d%c", WL->Words[i + SubStrCount].line, ", ", WL->Words[i + SubStrCount].pos, 'n');
         }
    }

    // Освобождение памяти
    free(DStr);

}

void Cutter(struct WordList * WL, unsigned int SubStrCount) {
    // Переменные
    unsigned int i;

    unsigned int delta = WL->count - 2 * SubStrCount + 2;


    for (i = SubStrCount; i < 2*(SubStrCount-1); i++) {
        WL->Words[i].line = WL->Words[i + delta].line;
        WL->Words[i].pos  = WL->Words[i + delta].pos;
        sprintf_s(WL->Words[i].Text, "%s", WL->Words[i + delta].Text);
    }
    WL->count = 2 * SubStrCount - 2;

}

WL->Words = (struct Word *)realloc(WL->Words, (WL->count + WL->allocated) * sizeof(struct Word));

a b a a b a b a a b a a
a b a a b b a b a a b a a b
a b a a b a b a a b a a b a a b a b a b a a b a b a a b a a b @