未分類

Repeated Substring Pattern

Go, LeetCode, String

Repeated Substring Pattern

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

1
2
3
4
5
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

1
2
3
Input: "aba"
Output: False

Example 3:

1
2
3
4
5
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
提示 解題應用
String KMP演算法

Default:

1
2
3
func repeatedSubstringPattern(s string) bool {
}

解答思路:

這題一開始想到的便是KMP演算法，雖然有用上KMP演算法最核心的部分，不過其實並不完全是在用該演算法，因為並不是拿來查找字串，而是用來計算後頭的字串與前綴字串的相似程度而已，所以基本上只要這個表出來就差不多完成了，至於實作方式雖然網路上有很多種，但基本上大同小異找自己容易理解的即可。

程式碼解說:

最主要是將該字串轉為前綴相似表，而有了該表之後如果此字串是由同一前綴組成，該表最後一個數字就是組成該字串最後一個前綴最大的相似程度(也就是該前綴的長度)，最後只要判斷該數是否大於0(等於0就等於豆是完全不相似)，且【長度】與【長度減上前綴長度】兩數相除等於0就表示由相同前綴組成，

例如:

String: abcabcabc(長度9)

最大前綴: abcabc(長度6)

9%(9-6) = 0 (為同一前綴所組成)

1
2
3
4
5
6
func repeatedSubstringPattern(s string) bool {
	length := len(s)
	table := prefix(s)
	maxSubStrLen := table[len(table)-1]
	return maxSubStrLen > 0 && length%(length-maxSubStrLen) == 0
}

至於KMP演算法中的核心部分，也就是將字串轉為前綴的相似表，由於需要一步步推倒，建議可以看看GO社群中有人整理好關於KMP演算法的文章 [TIL] 有關字串搜尋的演算法: KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func prefix(s string) []int {
	i := 1
	j := 0
	length := len(s)
	table := make([]int, length+1)
	for i < length {
		if s[i] == s[j] {
			i++
			j++
			table[i] = j
		} else if j == 0 {
			i++
		} else {
			j = table[j]
		}
	}
	return table
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func repeatedSubstringPattern(s string) bool {
	length := len(s)
	table := prefix(s)
	maxSubStrLen := table[len(table)-1]
	return maxSubStrLen > 0 && length%(length-maxSubStrLen) == 0
}
func prefix(s string) []int {
	i := 1
	j := 0
	length := len(s)
	table := make([]int, length+1)
	for i < length {
		if s[i] == s[j] {
			i++
			j++
			table[i] = j
		} else if j == 0 {
			i++
		} else {
			j = table[j]
		}
	}
	return table
}

總結:

要判斷一字串中是否由相同的前綴字所組成，最快的方式就是利用KMP演算法中計算前綴字的相似程度，有了該相似表如果都是由同一前綴字所組成就可以找出該同綴字，進而判斷字串是否由相同的前綴字所組成。

分享到