POJ 1750 - Dictionary

http://poj.org/problem?id=1750

概要

与えられた単語の列を，問題文に書いてあるルールに従ってインデントして答える．

が，そのルールの意味が全くわからなかったので Sample Input からエスパーするゲーム．

制約

• 単語の数は 10^5 以下
• 1つの単語は1文字以上10文字以下の小文字

解法

エスパーの結果，「i 行目のインデント = min(i-1 行目のインデント + 1, i-1 番目の単語と i 番目の単語を先頭から見ていったときに一致する文字の数)」であることが判明したので，そのように書くだけ．

TLE が厳しめなので C 文字列で．

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int next_offset(int off, const char *prev, const char *cur)
 6 {
 7   int i, j, k;
 8   for (i = j = k = 0;
 9       i < off+1 && prev[j] != '\0' && cur[k] != '\0' && prev[j] == cur[k];
10       ++i, ++j, ++k);
11   return i;
12 }
13 
14 void indent(int n)
15 {
16   for (int i = 0; i < n; i++) {
17     putchar(' ');
18   }
19 }
20 
21 int main()
22 {
23   char prev[16], cur[16];
24   scanf("%s", prev);
25   puts(prev);
26   for (int off = 0; scanf("%s", cur) != EOF; memcpy(prev, cur, 11)) {
27     off = next_offset(off, prev, cur);
28     indent(off);
29     puts(cur);
30   }
31   return 0;
32 }