CODEWITHSUNDEEP
c++inputnewline
Marijus
Marijus

Reputation: 4365

input, output and \n's

So I'm trying to solve this problem that asks to look for palindromes in strings, so seems like I've got everything right, however the problem is with the output.

Here's the original and my out put: http://pastebin.com/c6Gh8kB9

Here's whats been said about input and input of the problem:

Input format :

A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).

Output format :

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

Here's how I read the input :

string test;
string original;

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

And here's how I output it:

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() is a function to remove the illegal characters from the beginning and the end. I'm guessing that the problem is with \n's and the way I read the input. How can I fix this ?

Upvotes: 1

Views: 290

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490098

After rereading, it appears that I misunderstood the question. I was thinking in terms of each line representing a single word, and the intent is to test whether that "word" is palindromic.

After rereading, I think the question is really more like: "Given a sequence of up to 20,000 characters, find the longest palindromic sub-sequence. Oh, incidentally, the input is broken up into lines of no more than 80 characters."

If that's correct, I'd ignore the line-length completely. I'd read the entire file into a single buffer, then search for palindromes in that buffer.

To find the palindromes, I'd simply walk through each position in the array, and find the longest possible palindrome with that as its center point:

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]

Upvotes: 1

Fred Foo
Fred Foo

Reputation: 363517

No line is longer than 80 characters (not counting the newline at the end)

does not imply that every line is 80 characters except for the last, while your output code does assume this by taking 80 characters off answer in every iteration.

You may want to keep the newlines in the string until the output phase. Alternatively, you might store newline positions in a separate std::vector. The first option complicates your palindrome search routine; the second your output code.

(If I were you, I'd also index into answer instead of taking chunks off with substr/erase; your output code is now O(n^2) while it could be O(n).)

Upvotes: 2

Related Questions