切換
舊版
前往
大廳
主題

ZeroJudge - e682: 00531 - Compromise　解題心得

Not In My Back Yard | 2020-02-24 01:04:28 | 巴幣 0 | 人氣 309
題目連結：
題目大意：
輸入有多筆測試資料，每筆有兩句話。每句話有不超過 100 個單字組成並以「#」作結。每個單字由少於 30 個小寫英文字母所構成，彼此間以空格分開。

對於每筆測資，求出該兩句話的最長共同單字子序列（保證至少有一共同字詞）。

範例輸入：
die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#
範例輸出：
die einkommen der abgeordneten muessen dringend verbessert werden
解題思維：
將每個單字是作單一字元，並忽略所有空白字元。所求就成了最長共同子序列（Longest Common Subsequence，LCS）。因此，就比照 LCS 的做法即可（如這題），但是要記錄過程中的單字。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#動態規劃（Dynamic Programming）#最長共同子序列（Longest Common Subsequence）
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

速度所帶來的快感 🏎️

看更多

更多創作

追蹤 創作集
其他創作
作品資料夾