🔗 UVA-11576

tags: `字串(String)`

範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

電子滾動顯示器(Electric scrolling signs) 有固定的顯示字元數，每次滾動時會將最左邊的字元移出，並在最右邊添加一個新字元，我們的目標是通過最少的字元滾動數來顯示一系列指定的單字。

舉例來說，假設顯示器有 $3$ 個字元位置，訊息中包含 $3$ 個單字 $[\textit{CAT}, \textit{ATE}, \textit{TED}]$ ，則需要滾動 $5$ 個字元才能顯示所有單字。

顯示第一個單字 $\textit{CAT}$ 需要滾動 $3$ 個字元： $\textit{C}, \textit{A}, \textit{T}$ 。
接著顯示第二個單字 $\textit{ATE}$ ，可以利用第一個單字中的最後兩個字元 $\textit{A}$ 和 $\textit{T}$ ，只需要再滾動 $1$ 個字元： $\textit{E}$ 。
最後顯示第三個單字 $\textit{TED}$ ，可以利用第二個單字中的最後兩個字元 $\textit{T}$ 和 $\textit{E}$ ，只需要再滾動 $1$ 個字元： $\textit{D}$ 。

給定能夠顯示的字元數 $n = k$ 和 $m = w$ 個長度為 $n$ 的單字，請求出 最少需要滾動的字元數 。

約束條件

$1 \leq n \leq 100$
$1 \leq m \leq 100$

思路：字串(String)

由於可以和前一個單字重複使用部分字元，我們可以透過比較相鄰的兩個單字，找到可以共用字元的位置，從而減少需要滾動的字元數量。

初始化答案 $ans = n * m$ ，若每個單字都需要滾動 $n$ 個字元，則總共需要滾動 $n * m$ 個字元。

對於相鄰的兩個單字 $wa$ 和 $wb$ ，我們透過檢查每個 $wa$ 的後綴和 $wb$ 的前綴，找到它們的最大重疊部分，並減去不必要的滾動字元數，即 $wa[i:] = wb[:n-i]$ ，其中 $n - i$ 為重疊部分的長度。

複雜度分析

時間複雜度： $\mathcal{O}(m \cdot n^2)$ $O (m \cdot n^{2})$
- 每個測試案例中，我們需要比較 $m-1$ 對相鄰單字的各種重疊情況。每個單字長度為 $n$ ，需要從長度為 $n$ 開始檢查最大重疊部分，總共檢查 $n$ 種長度。
空間複雜度： $\mathcal{O}(m \cdot n)$ ，主要用於儲存單字列表。

T = int(input())

for _ in range(1, T+1):
    n, m = map(int, input().split())
    words = [input() for _ in range(m)]

    ans = n * m
    for i in range(m-1):
        wa, wb = words[i], words[i+1]
        for i in range(n):
            if wa[i:] == wb[:n-i]:
                ans -= n - i
                break
    print(ans)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int t, n, m, ans;
	cin >> t;
	while (t--) {
        ans = 0;
		cin >> n >> m;
		vector<string> words(m);
		for (int i=0; i<m; i++){
			cin >> words[i];
		}
		ans = n * m;
		for (int i=0; i<m-1; i++){
			for (int j=0; j<n; j++){
                if (words[i].substr(j) == words[i+1].substr(0, n-j)){
                    ans -= n - j;
                    break;
                }
            }
		}
        cout << ans << endl;
	}
}