31 . 宇宙語
TopCoder
Tags
Description
「BONAN」
「MATENON」
為了能夠與更多外星人溝通，海果決定要更努力的學習宇宙語！
每個宇宙語的句子都是由數個宇宙語符號組合成的。而海果發現只要句子中出現連續相同的符號，或句子開頭的符號與結尾的符號相同，她就需要花更多的力氣背。對此，她定義一個句子是難記的若它滿足以下兩條件：
- 該句子的符號數量至少為 $2$
- 該句子的開頭符號與結尾符號相同，或存在兩相鄰且相同的符號
舉例來說，下圖顯示了三個宇宙語句子，前兩個都是難記的，而最後一個不是：
PEGGJOV=MOVLOV,PIVOU,BOVVU=VUV ANTAŬDIRITA KAMARADO
了解到哪些句子是難記的後，海果想要將一個大句子拆解成許多段小句子，使得每一個小句子都不是難記的，同時盡可能最小化小句子的數量來幫助她快速記憶（注意是數量不是種類）。
更明確的說，假設一句子有 $n$ 個符號 $s_1s_2\ldots s_n$，請找到最小的 $k$ 使得存在 $l_1, r_1, l_2, r_2, \ldots, l_k, r_k$ 滿足：
- $\forall 1 \leq i \leq k, l_i \leq r_i$
- $\forall 1 \leq i < k, r_i + 1 = l_{i + 1}$
- $l_1 = 1, r_k = n$
- $\forall 1 \leq i \leq k, s_{l_i}s_{l_i + 1}\ldots s_{r_i}$ 這個句子是不難記的
但海果不太擅長做這件事，現在給定她想要背的 $N$ 個句子，對於每一個句子，你能幫助她計算至少需要拆解成幾個小句子嗎？
Input Format
輸入第一行有一個整數 $N$，代表句子的數量。
接下來 $N$ 行，第 $i$ 行有一個字串 $s_i$，代表第 $i$ 個句子的內容。輸入會用可視字元來表示宇宙語的符號，若兩字元相同則代表兩者為相同的宇宙語符號，否則則代表不同。輸入的字元包含：
QWXY以外的大寫英文字母- 小寫英文字母
cghjsu - 等於
= - 逗號
,
資料範圍：
- $1 \leq N \leq 2 \times 10^ 5$
- $\sum\limits_{i = 1}^ {N}|s_i| \leq 2 \times 10^ 5$
Output Format
請輸出 $N$ 行，第 $i$ 行請輸出一個正整數，代表第 $i$ 個句子至少需要拆解成幾個小句子。
Sample Input 1
6
AABA
CCCCCC
PEGGJOV=MOVLOV,PIVOU,BOVVU=VUV
ANTAuDIRITA
KAMARADO
g=cc,,==j==s,,uu,c==cc,=j
AABA
CCCCCC
PEGGJOV=MOVLOV,PIVOU,BOVVU=VUV
ANTAuDIRITA
KAMARADO
g=cc,,==j==s,,uu,c==cc,=j
Sample Output 1
3
6
4
2
1
10
6
4
2
1
10
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~29 | 無其他限制 | 100 |