給定一個英文字串,找到第一個出現且有最長不重複英文字母的子字串, 並輸出該子字串內容及長度。該子字串需滿足下列條件: (1)為原輸入字串之子字串。 (2)擁有最長不同字母長度。 (3)子字串中英文字母不重複。 (4)如有多個不重複子字串,其長度皆相同時,則列出由左到右, 順序為第一個出現的子字串。 例如:輸入字串 "pwwkew",輸出答案為 "wke 3";此題中,有子字串 "wke" 及 "kew" 長度均為 3,依條件 (5)答案須列出由左到右,順序為第一個出現的子字串,即 "wke"。 輸入說明 輸入英文字串,大小寫視為相異。 輸出說明 輸出符合上述性質之最長子字串及其長度,兩者間以空格隔開。
此題演算法不難,不能算是經典的字串難題,答題者,對該題心中應該 知道搜尋字串的效率應該是 O(n)。 另外,此題會有測資 字串為 a 時,程式如何應對? 家豪版 Dim locat(122) As Integer "小寫英文字母 ascii = 122 Dim maxS As String, strL As Integer "最長字母, 與長度 Dim i As Integer, j As Integer, c As Byte, dif As Integer, maxL As Integer, tc As String Dim tmp As String = TextBox1.Text, tmpL As Integer = TextBox1.Text.Length() - 1 strL = 0 : dif = 0 : maxL = 0 : maxS = "" Do While (i <= tmpL) c = Asc(tmp.Substring(i, 1)) If (locat(c) > 0) Then "前面已經有該字母了 dif = locat(c) For j = 0 To dif - 1 locat(Asc(tmp.Substring(j, 1))) = 0 Next For j = dif To i - 1 locat(Asc(tmp.Substring(j, 1))) -= dif Next locat(Asc(tmp.Substring(i, 1))) = i tc = tmp.Substring(0, i) tmp = tmp.Substring(dif) If (tc.Length() > maxS.Length()) Then maxS = tc i -= dif - 1 : tmpL -= dif Else i += 1 locat(c) = i End If Loop If maxS = "" Then maxS = TextBox1.Text "若未找到最大字串,則本身即是 TextBox2.Text = maxS & " " & maxS.Length() 昊朋版 黃翰版 |