Initial

4 files changed, 170 insertions, 0 deletions

diff --git a/subseq/doc.go b/subseq/doc.go
new file mode 100644
index 0000000..4e4282c
--- /dev/null
+++ b/subseq/doc.go
@@ -0,0 +1,2 @@
+// Пакет с функциями получения подпоследовательностей (например, подстроки)
+package subseq
diff --git a/subseq/generic.go b/subseq/generic.go
new file mode 100644
index 0000000..4415ffb
--- /dev/null
+++ b/subseq/generic.go
@@ -0,0 +1,80 @@
+package subseq
+
+func MaxSubset[T comparable](s1, s2 []T) []T {
+	len1 := len(s1)
+	len2 := len(s2)
+
+	dp := make([][]int, len1+1)
+	for i := range dp {
+		dp[i] = make([]int, len2+1)
+	}
+	max := 0
+	u := 0
+	for i := 0; i < len1; i++ {
+		for j := 0; j < len2; j++ {
+			switch {
+			case i == 0:
+				dp[0][j] = 0
+			case j == 0:
+				dp[i][0] = 0
+			case s1[i] != s2[j]:
+				dp[i][j] = 0
+			default:
+				dp[i][j] = dp[i-1][j-1] + 1
+				if dp[i][j] > max {
+					max = dp[i][j]
+					u = i
+				}
+			}
+		}
+	}
+	ret := []T{}
+	for i := max; i > 0; i-- {
+		ret = append(ret, s1[u-i+1])
+	}
+	return ret
+}
+
+func MaxSubsetSequence[T comparable](s1, s2 []T) []T {
+	len1 := len(s1)
+	len2 := len(s2)
+
+	dp := make([][]int, len1+1)
+	for i := range dp {
+		dp[i] = make([]int, len2+1)
+	}
+
+	for i := len1; i >= 0; i-- {
+		for j := len2; j >= 0; j-- {
+			switch {
+			case i == len1, j == len2:
+				dp[i][j] = 0
+			case s1[i] == s2[j]:
+				dp[i][j] = 1 + dp[i+1][j+1]
+			default:
+				max := dp[i+1][j]
+				if dp[i][j+1] > max {
+					max = dp[i][j+1]
+				}
+				dp[i][j] = max
+			}
+		}
+	}
+
+	ret := []T{}
+	i, j := 0, 0
+	for i < len1 && j < len2 {
+		switch {
+		case s1[i] == s2[j]:
+			ret = append(ret, s1[i])
+			i++
+			j++
+		case dp[i+1][j] >= dp[i][j+1]:
+			i++
+		default:
+			j++
+		}
+	}
+
+	return ret
+}
diff --git a/subseq/strings.go b/subseq/strings.go
new file mode 100644
index 0000000..6be73e9
--- /dev/null
+++ b/subseq/strings.go
@@ -0,0 +1,11 @@
+package subseq
+
+// MaxSubstring возвращаает максимальную общую подстроку
+func MaxSubstring(s1, s2 string) string {
+	return string(MaxSubset([]rune(s1), []rune(s2)))
+}
+
+// MaxSubsequence возвращает максимальную общую подпоследовательность символов
+func MaxSubsequence(s1, s2 string) string {
+	return string(MaxSubsetSequence([]rune(s1), []rune(s2)))
+}
diff --git a/subseq/strings_test.go b/subseq/strings_test.go
new file mode 100644
index 0000000..b35b139
--- /dev/null
+++ b/subseq/strings_test.go
@@ -0,0 +1,77 @@
+package subseq
+
+import (
+	"testing"
+)
+
+func TestMaxSubstring(t *testing.T) {
+	type args struct {
+		s1 string
+		s2 string
+	}
+	tests := []struct {
+		name string
+		args args
+		want string
+	}{
+		{
+			name: "test",
+			args: args{
+				s1: "какая то строка текста",
+				s2: "другая строка другого",
+			},
+			want: " строка ",
+		},
+		{
+			name: "test2",
+			args: args{
+				s1: "qwertyuiop",
+				s2: "asdfghertyjklzxcvzxqertyuvzvb",
+			},
+			want: "ertyu",
+		},
+		{
+			name: "empty",
+			args: args{
+				s1: "abc",
+				s2: "def",
+			},
+			want: "",
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if got := MaxSubstring(tt.args.s1, tt.args.s2); got != tt.want {
+				t.Errorf("MaxSubstring() = %v, want %v", got, tt.want)
+			}
+		})
+	}
+}
+
+func TestMaxSubseq(t *testing.T) {
+	type args struct {
+		s1 string
+		s2 string
+	}
+	tests := []struct {
+		name string
+		args args
+		want string
+	}{
+		{
+			name: "test",
+			args: args{
+				s1: "nematode knowledge",
+				s2: "empty bottle",
+			},
+			want: "emt ole",
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if got := MaxSubsequence(tt.args.s1, tt.args.s2); got != tt.want {
+				t.Errorf("MaxSubseq() = %v, want %v", got, tt.want)
+			}
+		})
+	}
+}