Talk:Longest string challenge: Difference between revisions
Content added Content deleted
Line 348: | Line 348: | ||
::::: What do you think of the version I added? --[[User:Rdm|Rdm]] 21:02, 17 August 2011 (UTC) |
::::: What do you think of the version I added? --[[User:Rdm|Rdm]] 21:02, 17 August 2011 (UTC) |
||
:::::: <code>if (!longer(bufend, line))</code> isn't really checking for accumulator overflow, is it? Also, if you use <code>memset</code> to mark unused buffer region, they should to be called every time the accumulator is reset (i.e. found a new longest line), or it would be possible that there's a null byte in the tail region of <code>buf</code> before the reset, but accumulated strings haven't reached there yet, and next <code>if (!longer(bufend, line))</code> can give a false positive on overflow. (I think) --[[User:Ledrug|Ledrug]] 21:24, 17 August 2011 (UTC) |
:::::: <code>if (!longer(bufend, line))</code> isn't really checking for accumulator overflow, is it? Also, if you use <code>memset</code> to mark unused buffer region, they should to be called every time the accumulator is reset (i.e. found a new longest line), or it would be possible that there's a null byte in the tail region of <code>buf</code> before the reset, but accumulated strings haven't reached there yet, and next <code>if (!longer(bufend, line))</code> can give a false positive on overflow. (I think) --[[User:Ledrug|Ledrug]] 21:24, 17 August 2011 (UTC) |
||
:::::EDIT yes that does happen. Modified the code to this: (LINE_MAX is your 1000000, your buffer would have been <code>#define ACCU_MAX (11*LINE_MAX + 1)</code>, but the point is the same:<lang c>#define LINE_MAX 6 |
|||
#define ACCU_MAX (4*LINE_MAX+1) |
|||
int main() { |
|||
char line[LINE_MAX]; |
|||
char buf[ACCU_MAX]; |
|||
char *linend= &line[LINE_MAX - 1]; |
|||
char *bufend= &buf[ACCU_MAX - LINE_MAX - 1]; |
|||
char *last = buf; |
|||
char *next = buf; |
|||
memset(line, 1, LINE_MAX); |
|||
memset(buf, 1, ACCU_MAX); |
|||
buf[0]= buf[ACCU_MAX - 1]= 0; |
|||
while (fgets(line, LINE_MAX, stdin)) { |
|||
if (!*linend) exit(1); |
|||
if (longer(last, line)) continue; |
|||
if (!longer(bufend, line)) exit(1); |
|||
if (longer(line, last)) next = buf; |
|||
last = next; |
|||
strcpy(next, line); |
|||
while (*next) next = &next[1]; |
|||
}</lang> and it aborts on the input <code>echo "aa\nbb\ncc\ndd\nee\nff\naaa" | ./a.out</code> but works if you remove any of the doubles. --[[User:Ledrug|Ledrug]] 21:28, 17 August 2011 (UTC) |
|||
== Boring solution v. restrictions == |
== Boring solution v. restrictions == |