Java: читать содержимое входного файла и фильтровать его, если найдены последовательности строк

Question

Мне нужно обработать входной файл и скопировать его содержимое (строка ilne) в выходной файл. Однако в этом входном файле есть некоторые неважные данные (блуждающие), которые мне нужно пропустить. Основная проблема, которую я пытаюсь решить, на самом деле более сложная, чем эта, но я просто собираюсь упростить задачу:

Итак, у меня есть входной файл, содержащий сотни тысяч строк. Если во входном файле присутствует следующая последовательность из 3 строк:
A
B
С

тогда мне нужно пропустить эти 3 строки и перейти к следующей строке во входном файле. Я могу пропустить эти 3 строки, только если эти 3 строки представляют собой последовательность последовательных строк.

Например:
Входной файл:

A
A
B
C
B
P
A
B
С * * тысяча двадцать-один A
B
A
A
B
C
A

Выходной файл:
A
B
P
A
B
A
A

Пояснение:
A
A (пропущено)
B (пропущено)
C (пропущено)
B
P
A (пропущено)
B (пропущено)
C (пропущено)
A
В
A
A (пропущено)
B (пропущено)
C (пропущено)
A

Обратите внимание, что я могу пропустить последовательность строк (A, B, C), только если они происходят последовательно. Все остальные строки, которые не пропущены, должны быть скопированы в выходной файл. Если я использую BufferedReader.nextLine (), я не могу вернуться к предыдущим строкам, если следующая строка не соответствует шаблону ввода. Например, если я уже столкнулся с A, а следующая строка - это другая A (не B), я должен скопировать первый A в выходной файл и снова начать фильтрацию со второго A, который я не обработал, и проверьте следующую следующую строку и так далее.

Один из способов, который я могу придумать, - это сначала сохранить содержимое входного текстового файла, чтобы я мог легко вернуться при обходе содержимого входного файла, если он не соответствует шаблону, который я ищу. Однако это не решение для памяти. Есть ли какой-нибудь умный алгоритм для решения этой проблемы, предпочтительно за один раз, то есть O (N) сложность? Или, если это невозможно, что было бы наиболее оптимальным решением, которое по-прежнему связано с памятью? Некоторые примеры C / Java-кодов будут действительно полезны.

Answer 1

Я предполагаю, что ваши строки более сложные, чем просто "A", "B" и "C", но есть какой-то способ выбрать "A" из "B" из "C".

(Если это действительно A, B и C, то вам не нужно ничего хранить)

Я бы сделал небольшую программу типа конечного автомата.

state = Base;
while(there are more lines)
{   
    line = read_a_line()
    switch(state) {
        case Base:
          if (line.isTypeA()) {
            storedLines.add(line);
            state = GotA;
          }
          else {
             ouput(line);
          }
          break;
        case GotA:
          if (line.isTypeB()) {
            storedLines.add(line);
            state = gotB;
          }
          else {
              output(storedLines);
              output(line);
              state = Base;
          }
          break;
        case GotB:
          if (line.isTypeC()) {
            storedLines.clear();
          }
          else {
              output(storedLines);
              output(line);
          }
          state = Base;
          break;
    }
    // TODO: special case handling to make sure you write everything at the end of the
    // file.

Answer 2

Вы можете сделать это с 3-элементным массивом.

Всякий раз, когда вы сталкиваетесь с A, проверьте, пуст ли первый элемент массива - если нет, сбросьте массив в выходной файл - затем сохраните новый A в первом элементе массива.

Всякий раз, когда вы встречаете B, проверьте, если второй элемент массива пуст, но первый элемент заполнен - ​​если нет, сбросьте массив в выходной файл вместе с новым B. В противном случае (то есть, если первый элемент заполнен, но второй пуст), вы сохраните новый B как второй элемент массива.

Для C, повторите логику для B, увеличенную на единицу: всякий раз, когда вы сталкиваетесь с C, проверьте, если третий элемент массива пуст, но 2-й элемент заполнен - ​​если нет, сбросьте массив в выходной файл вместе с новым C. В противном случае (то есть, если 2-й элемент заполнен, а 3-й пуст), вы сохраните новый C в качестве 3-го элемента массива.

Если вы не встретите ни A, ни B, ни C, сбросьте все существующие элементы массива в выходной файл, а затем запишите новую строку непосредственно в выходной файл.

Основной трюк здесь заключается в том, что вы определяете явные правила для заполнения каждого слота буферного массива и используете это, чтобы избежать повторной проверки совпадений строк, сбрасывая буфер на выход и сбрасывая последовательность всякий раз, когда вы прерываете шаблон.

Конечно, вы признаете, что ваш фактический набор правил несколько сложнее, но подход того же типа должен работать.

Answer 3

Вы можете использовать mark и сбросить в вашем потоке, чтобы "перемотать"