1452 . 截然不同
TopCoder
Tags
Description
請注意本題的記憶體限制為 16 MB。
對於兩個長度相同的字串 $S, T$，如果不存在任何一個 $i$ 滿足 $1 \le i \le \lvert S \rvert$ 且 $S$ 的第 $i$ 個字元 $= T$ 的第 $i$ 個字元，我們說 $S$ 與 $T$ 截然不同。 例如 ababa 與 cdbab 截然不同，但 bdcac 與 cdabd 就不是截然不同。
今天，Ina 給了 pooh $N$ 個長度為 $5$ 的字串 $S_1, S_2, \dots, S_N$，並給了 pooh 這樣的一個挑戰：
定義 $f(i)$ 為所有滿足 $1 \le j < i$ 且滿足 $S_j$ 與 $S_i$ 截然不同的最大的 $j$，如果不存在任何滿足條件的 $j$ 則定義 $f(i)$ 為 $0$，要求 pooh 對於所有 $1 \le i \le N$ 計算 $f(i)$ 的值。而 pooh 決定求助於你，請你寫一個程式幫助他解決這個挑戰。
Input Format
輸入第一行有一個正整數 $N$。
接下來 $N$ 行，每行有一個長度為 $5$ 的字串，依序為 $S_1, S_2, \dots, S_N$。
- $1 \le N \le 2\times 10^ 5$
- 所有字串都由非空白與換行的 ASCII 可視字元構成
Output Format
總共輸出 $N$ 行，第 $i$ 行為一個非負整數，代表 $f(i)$。
Sample Input 1
5 Ninom aeIna nisWA HejwA fnioo
Sample Output 1
0 1 2 1 4
Sample Input 2
5 cabab babbc acaba bacca abcab
Sample Output 2
0 0 1 0 2
Hints
請注意時空間限制與程式本身的常數和效率。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~11 | $N \le 1000$ | 5 |
| 3 | 12~24 | 所有字串都由 ${a, b, c }$ 構成。 | 25 |
| 4 | 0~50 | 無特別限制。 | 70 |