My eye is drawn to this:

It seems to me that the repeated .* is likely to result in a lot of backtracking during the match of the regex. I suggest you try replacing the first two .* expressions with something like [^\[]+ and add a $ anchor at the end. That would change that line to:

There may be something more elegant you could do (and somebody will chip in) but I bet that will result in a speed improvement.

Mind you, the O n^2 algorithm won't help.