Тут и я, не зная английского, разобью второй столбец на два, а программа тем более.

К чему этот поиск вырожденных случаев, вероятность которых мала?

1. Выделять память нужно только под позиции пробелов, причем их будет сначала столько, сколько в первой строке, потом только уменьшаться.
2. Пересечение двух отсортированных списков (а они будут сразу отсортированные) О(n).
3. Не надо бежать по всем строкам, достаточно некоторого разумного количества.
4. Есть еще варианты? Если нет -- придется использовать этот :)

Да, этот вариант самый оптимальный, но и он не даст нормальной точности.

Тут и человек не даст нормальной точности.

Вариант с нормальными разделителями столбцов дал бы 100% точность.

ZoNT, эмпирические методы как раз и используются, когда задача не решается на 100%. И они позволяют задачу решить в большинстве случаев. Это же лучше, чем вообще не решить задачу?

Правильное решение - избежать нерешаемых задач, то есть заранее спроектировать систему так, чтобы избежать таких ситуаций.

по поводу эмпирических методов
p.s. т.е. ты считаешь, что можно _всегда_ предусмотреть все варианты и учесть все интересы?

Нет, но можно выбрать удобные инструменты для работы. Зачем парсить такой вывод, который делает сиджиайка, если можно переписать сиджиайку, чтобы она ставила нормальные разделители?

это не всегда разумно (требуется намного больше усилий)