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

typedef char bool;
#define true 1
#define false 0
/* compare strings via pointers */
bool pstrcmp(const void *p1, const void *p2)
{
    return strcmp(*(char * const *)p1, *(char * const *)p2);
}

bool isChar(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

void addSymb(char** strings, int idMain, int* id, int* allocatedSize, char c) {
//    printf("%s %d %d %d %c\n", "addSymb:", idMain, *id, *allocatedSize, c);
    if (*id == 0)
        strings[idMain] = malloc(sizeof(char*));
    if (*id == *allocatedSize - 1) {
        *allocatedSize = 2 * *allocatedSize + 1;
        strings[idMain] = realloc(strings[idMain], (*allocatedSize) * sizeof(char));
    }
    strings[idMain][*id] = c;
    (*id)++;
}

void addString(char*** strings, int* idMain, int* id, int* allocatedSizeMain, int* allocatedSize, bool* toPushString) {
    *toPushString = false;
//    printf("%s %d %d %d %d\n", "addString:", *idMain, *id, *allocatedSizeMain, *allocatedSize);
    (*strings)[*idMain][*id] = 0;
//      printf("%s\n", (*strings)[*idMain]);
    if (*idMain == *allocatedSizeMain - 1) {
        *allocatedSizeMain = 2 * *allocatedSizeMain + 1;
        *strings = realloc(*strings, *allocatedSizeMain * sizeof(char*));
    }
    *allocatedSize = 0;
    *id = 0;
    (*idMain)++;
    (*strings)[*idMain] = malloc(sizeof(char*));
}

void freeMemory(char** strings, int n) {
    for (int i =0 ; i < n; i++)
        free(strings[i]);
    free(strings);
}

void print(char** strings, int idMain) {
     printf("%s\n", "_________->");
    for (int i = 0; i < idMain; i++) {
        printf("%s\n", strings[i]);
    }
    printf("%s\n", "<-_________");
}

int main(int argc, const char * argv[]) {
    char** strings = malloc(1 * sizeof(char*));
    char c  = ' ';
    int idMain = 0;
    int id = 0;
    int allocatedSize = 0;
    int allocatedSizeMain = 1;
    // fp = fopen(stdin, "r");
//    if (fp != NULL)
//        printf("%s\n", "file loaded");
//    else
//        printf("%s", "bad");
    int state = 0;
    bool eofFinded = false;
    bool toPushString = false;
    while (true) {
//        print(strings, idMain);
        switch(state) {
                //begin-space state
            case 0:
                if (isspace(c) || c == '\n') {
                    state = 0;
                    break;
                }
                if (isChar(c)) {
                    state = 1;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    break;
                }
                if (c == ';') {
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    break;
                }
                if (c == '&') {
                    state = 2;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    break;
                }
                if (c == '|') {
                    state = 3;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    break;
                }
                break;
                //word state
            case 1:
                if (isspace(c) || c == '\n') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    break;
                }
                if (isChar(c)) {
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    break;
                }
                if (c == ';') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    break;
                }
                if (c == '&') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 2;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    break;
                }
                if (c == '|') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 3;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    break;
                }
                break;
                //& state
            case 2:
                if (isspace(c) || c == '\n') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    break;
                }
                if (isChar(c)) {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    state = 1;
                    break;
                }
                if (c == ';') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    addSymb(strings, idMain, &id, &allocatedSize, ';');
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                }
                if (c == '&') {
                    //addString(strings, &idMain, &id, &allocatedSizeMain, &allocatedSize);
                    state = 0;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                }
                if (c == '|') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    state = 3;
                }
                break;
                // | state
            case 3:
                if (isspace(c) || c == '\n') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    break;
                }
                if (isChar(c)) {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    state = 1;
                    break;
                }
                if (c == ';') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                }
                if (c == '|') {
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    state = 0;
                }
                if (c == '&') {
                    addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
                    addSymb(strings, idMain, &id, &allocatedSize, c);
                    state = 2;
                }
                break;
        }
        if (state == 4) {
            if (c == EOF || eofFinded) {
                printf("%s\n", "right \" not found");
                freeMemory(strings, idMain);
                return 0;
            }
            if (c == '\"') {
                //addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize);
                toPushString = true;
                state = 0;
                // c = fgetc(fp);
                scanf("%c", &c);
                if (c == EOF) {
                    eofFinded = true;
                    c = ' ';
                }
                continue;
            }
            else
                addSymb(strings, idMain, &id, &allocatedSize, c);
        }
        if (state == 5) {
            if (c == EOF || eofFinded) {
                printf("%s\n", "right \' not found");
                freeMemory(strings, idMain);
                return 0;
            }
            if (c == '\'') {
                toPushString = true;
                //addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize);
                state = 0;
                // c = fgetc(fp);
                scanf("%c", &c);
                if (c == EOF) {
                    eofFinded = true;
                    c = ' ';
                }
                continue;
            }
            else
                addSymb(strings, idMain, &id, &allocatedSize, c);
        }
        if (eofFinded)
            break;
        if (c == '\"') {
            state = 4;
        }
        if (c == '\'') {
            state = 5;
        }

        // c = fgetc(fp);
        scanf("%c", &c);
        printf("%c\n", c);
        if (c == '#') {
            eofFinded = true;
            c = ' ';
        }
    }
    if (toPushString)
        addString(&strings, &idMain, &id, &allocatedSizeMain, &allocatedSize, &toPushString);
    printf("%s\n", "------");
    qsort(strings, idMain - 1, sizeof(char*) , pstrcmp);
    for (int i = 0; i < idMain; i++) {
        printf("\"%s\"\n", strings[i]);
    }
    return 0;
}