bugs.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstdio>
 
#define stackInit if (!stack.size()) { stack.push_back(0); stackTop = stack.rbegin(); emptyStack = true; }
#define stackPop(x) stack.pop_back(); if (stack.size()) { stackTop = stack.rbegin(); } if(x) { stackInit; }
#define stackPush(x) stack.push_back(x); if (stack.size()) { stackTop = stack.rbegin(); } stackInit;
 
//#define getc() fgetc(in)
#define getc() getc(stdin)
typedef unsigned int uint;
using namespace std;
 
uint lines;
string err;
char firstC = 0;
bool repeated;
vector<uint> stack;
bool emptyStack;
vector<uint>::reverse_iterator stackTop;
vector<pair<uint, uint> > toDoStack; //From - to
 
void printAllToDo() {
    for (vector<pair<uint, uint> >::reverse_iterator it = toDoStack.rbegin(); it != toDoStack.rend(); it ++) {
        for (uint j = it->first; j < it->second; j ++) {
            printf("%c", err[j]);
        }
    }
    toDoStack.clear();
}
 
void printAll() {
    for (vector<uint>::iterator it = stack.begin(); it != stack.end(); it ++) {
        for (uint j = 0; j < *it; j ++) {
            printf("%c", err[j]);
        }
    }
    stack.clear();
    stackInit;
}
inline void letterMatch() {
    (*stackTop)++;
    if (*stackTop == err.size()) { //Found BUG
        stackPop(true);
    }
}
 
bool apply(char c, bool dontFork) {
    if (*stackTop > 0) {
        if (c == firstC && !dontFork) {
            stackPush(1);
            return true;
        }
        else if (c == err[*stackTop]) {
            letterMatch();
            return true;
        }
    }
    else if (c == firstC) { //Start new one
        emptyStack = false;
        letterMatch();
        return true;
    }
    return false;
}
 
 
int main()
{
    //FILE* in = fopen("bugs.in", "r");
    while(true) {
        //if (fscanf(in, "%d", &lines) != 1) return 0;
        if (scanf("%d", &lines) != 1) return 0;
        if (getc() < 0) return 0; //space
        firstC = 0;
        repeated = false;
        for (char c = getc(); c != '\n'; c = getc()) {
            if (c < 0) return 0;
            err.push_back(c);
            if (!firstC) firstC = c;
            else if (firstC == c) repeated = true;
        }
        stackInit;
        pair<uint, uint> tmpPair = make_pair(0, 0);
        char c;
        for (uint i = 0; i < lines; i += (c == '\n' ? 1 : 0)) {
            c = getc();
            if (c < 0) return 0;
            bool wasFromStack = false;
            do {
                bool fromStack = toDoStack.size();
                const pair<uint, uint> &back = (fromStack ? toDoStack.back() : tmpPair );
                char d = (fromStack ? err[back.first] : c);
                if (apply(d, fromStack && back.first == 0)) { //Applied - good
                    if (fromStack) {
                        if ((back.first + 1) == back.second) { //Finished whole word
                            toDoStack.pop_back();
                        }
                        else {
                            toDoStack.rbegin()->first ++; //Increment if you did not
                        }
                    }
                    else wasFromStack = false;
                    continue;
                }
                if (emptyStack) {
                    printf("%c", c);
                    continue;
                }
                if (stack.size()) { //Did not applied
                    if (repeated) { //Need toDoStack
                        toDoStack.push_back(make_pair(0, *stackTop));
                        stackPop(false);
                        if (!stack.size()) {
                            printAllToDo();
                            printf("%c", c);
                            stackInit;
                            wasFromStack = false;
                        }
                        else wasFromStack = true;
                    }
                    else { //Do not need toDo stack
                        printAll();
                        printf("%c", c);
                        wasFromStack = false;
                    }
 
                }
            } while (toDoStack.size() || wasFromStack);
        }
        err.clear();
    }
 
    return 0;
}