ввод, вывод и \ n's - PullRequest
Новая
       22

ввод, вывод и \ n's

1 голос
/ 13 марта 2011

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

Вот оригинал и мойout put: http://pastebin.com/c6Gh8kB9

Вот что было сказано о вводе и вводе задачи:

Формат ввода:

Файл, содержащий не более 20 000 символов,Файл имеет одну или несколько строк.Длина строки не превышает 80 символов (не считая новой строки в конце).

Формат вывода:

Первая строка вывода должна быть длинойсамый длинный палиндром найден.Следующая строка или строки должны быть фактическим текстом палиндрома (без каких-либо окружающих пробелов или знаков пунктуации, но со всеми другими символами), напечатанными в строке (или более чем в одной строке, если в палиндромный текст включены новые строки).Если имеется несколько палиндромов самой длинной длины, выведите тот, который появляется первым.

Вот как я читаю ввод: 

string test;
string original;

while (getline(fin,test))
    original += test;

И вот как я вывожу его: 

int len = answer.length();
answer = cleanUp(answer);
while (len > 0){
    string s3 = answer.substr(0,80);
    answer.erase(0,80);
    fout << s3 << endl;
    len -= 80;
}

cleanUp () - это функция для удаления недопустимых символов в начале и в конце.Я предполагаю, что проблема в \ n и способе, которым я читаю ввод.Как я могу это исправить?

Ответы [ 2 ]

2 голосов
/ 13 марта 2011

Длина строки не превышает 80 символов (не считая перевода строки в конце)

не означает, что каждая строка содержит 80 символов, кроме последней, в то время как ваш выходной код предполагает это, снимая 80 символов answer в каждой итерации.

Возможно, вы захотите сохранить новые строки в строке до фазы вывода. Кроме того, вы можете хранить позиции новой строки в отдельном std::vector. Первый вариант усложняет вашу процедуру поиска палиндрома; второй ваш выходной код.

(На вашем месте я бы также занялся индексом answer вместо того, чтобы снимать фрагменты с помощью substr / erase; ваш выходной код теперь O ( n ^ 2), пока это может быть O ( n ).)

1 голос
/ 13 марта 2011

После перечитывания кажется, что я неправильно понял вопрос.Я думал с точки зрения каждой строки, представляющей отдельное слово, и целью было проверить, является ли это «слово» палиндромным.

После перечитывания, я думаю, что вопрос действительно больше похож на: «Учитывая последовательностьдо 20 000 символов, найдите самую длинную палиндромную подпоследовательность. О, кстати, ввод разбит на строки длиной не более 80 символов. "

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

Чтобы найти палиндромы, я бы просто прошел через каждую позицию в массиве и нашел бы максимально длинный палиндром с его центральной точкой: 

for (int i=1; i<total_chars; i++)
    for (n=1; n<min(i, total_chars-i); n++)
        if (array[i+n] != array[i-n])
            // Candidate palindrome is from array[i-n+1] to array[i+n-1]
...