Что такое алгоритм нахождения наименьшей общей подстроки (НОП) в Golang?

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

package main

import (
	"fmt"
)

func main() {
	str1 := "abcde"
	str2 := "cdeab"
	lcs := longestCommonSubstring(str1, str2)
	fmt.Println("Наименьшая общая подстрока:", lcs)
}

func longestCommonSubstring(str1, str2 string) string {
	var lcs string
	m := len(str1)
	n := len(str2)

	lcsMatrix := make([][]int, m+1)
	for i := 0; i < m+1; i++ {
		lcsMatrix[i] = make([]int, n+1)
	}

	maxLength := 0
	endingIndex := m

	for i := 1; i < m+1; i++ {
		for j := 1; j < n+1; j++ {
			if str1[i-1] == str2[j-1] {
				lcsMatrix[i][j] = lcsMatrix[i-1][j-1] + 1
				if lcsMatrix[i][j] > maxLength {
					maxLength = lcsMatrix[i][j]
					endingIndex = i
				}
			} else {
				lcsMatrix[i][j] = 0
			}
		}
	}

	if maxLength == 0 {
		return ""
	}

	startingIndex := endingIndex - maxLength
	lcs = str1[startingIndex:endingIndex]
	return lcs
}

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package main

import (
	"fmt"
	"math"
)

func main() {
	str1 := "abcde"
	str2 := "cdeab"
	lcs := shortestCommonSubstring(str1, str2)
	fmt.Println("Наименьшая общая подстрока:", lcs)
}

func shortestCommonSubstring(str1, str2 string) string {
	m := len(str1)
	n := len(str2)

	// Создание матрицы для хранения результатов
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}

	// Инициализация первого столбца и строки
	for i := 0; i <= m; i++ {
		dp[i][0] = 0
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = 0
	}

	// Вычисление значений dp[i][j] для всех i, j
	maxLen := 0
	endIndex := 0
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if str1[i-1] == str2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				if dp[i][j] > maxLen {
					maxLen = dp[i][j]
					endIndex = i - 1
				}
			} else {
				dp[i][j] = 0
			}
		}
	}

	// Восстановление наименьшей общей подстроки
	startIndex := endIndex - maxLen + 1
	substr := str1[startIndex : endIndex+1]
	return substr
}