1 #Region "Microsoft.VisualBasic::2bb189ec23f58f669e1bf17338d3f854, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\SCS.vb"
2
3     ' Author:
4     
5     '       asuka (amethyst.asuka@gcmodeller.org)
6     '       xie (genetics@smrucc.org)
7     '       xieguigang (xie.guigang@live.com)
8     
9     ' Copyright (c) 2018 GPL3 Licensed
10     
11     
12     ' GNU GENERAL PUBLIC LICENSE (GPL3)
13     
14     
15     ' This program is free software: you can redistribute it and/or modify
16     ' it under the terms of the GNU General Public License as published by
17     ' the Free Software Foundation, either version 3 of the License, or
18     ' (at your option) any later version.
19     
20     ' This program is distributed in the hope that it will be useful,
21     ' but WITHOUT ANY WARRANTY; without even the implied warranty of
22     ' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23     ' GNU General Public License for more details.
24     
25     ' You should have received a copy of the GNU General Public License
26     ' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30     ' /********************************************************************************/
31
32     ' Summaries:
33
34     '     Module SCS
35     
36     '         Function: Coverage, MaxPrefixLength, ShortestCommonSuperString
37     
38     '         Sub: TableView
39     
40     
41     ' /********************************************************************************/
42
43 #End Region
44
45 Imports System.IO
46 Imports System.Runtime.CompilerServices
47 Imports Microsoft.VisualBasic.Language
48
49 Namespace ComponentModel.Algorithm
50
51     ''' <summary>
52     ''' shortest_common_superstring
53     ''' </summary>
54     ''' <remarks>
55     ''' https://github.com/aakash01/codebase/blob/60394bf92eb09410c07eec1c4d3c81cf0fc72a70/src/com/aakash/practice/interviewbit_may2017/dynamic_programming/ShortestCommonSuperString.java
56     ''' </remarks>
57     Public Module SCS
58
59         <Extension>
60         Public Sub TableView(fragments As IEnumerable(Of String), SCS$, ByRef print As TextWriter, Optional empty As Char = "."c)
61             Dim lines As New List(Of String)
62
63             Call print.WriteLine(SCS)
64
65             For Each str As String In fragments
66                 Dim start% = InStr(SCS, str) - 1
67                 Dim ends% = start + str.Length
68                 Dim lefts = SCS.Length - ends
69                 Dim view$ = New String(empty, start) & str & New String(empty, lefts)
70
71                 lines += view
72             Next
73
74             Call print.WriteLine($"#Coverage={Coverage(lines, blank:=empty)}")
75             Call print.WriteLine(lines.JoinBy(print.NewLine))
76             Call print.Flush()
77         End Sub
78
79         ''' <summary>
80         ''' 使用重叠程度最高的片段作为统计的标准
81         ''' </summary>
82         ''' <param name="table"></param>
83         ''' <returns></returns>
84         Public Function Coverage(table As IEnumerable(Of String), Optional blank As Char = "."c) As Integer
85             ' 重叠程度最高,意味着blank是最少的
86             Dim lines As Char()() = table.Select(Function(s) s.ToArray).ToArray
87             ' 因为都是等长的,所以直接使用第一条作为标准了
88             Dim length% = lines(Scan0).Length
89             Dim coverages As New List(Of Integer)
90             Dim index%
91
92             For i As Integer = 0 To length - 1
93                 index = i
94                 coverages += lines _
95                     .Where(Function(seq)
96                                Return seq(index) <> blank
97                            End Function) _
98                     .Count
99             Next
100
101             Return coverages.Max
102         End Function
103
104         ''' <summary>
105         ''' Solve using Greedy. Forf all string find the max common prefix/suffix. Merge those two strings
106         ''' and continue it.
107         ''' </summary>
108         ''' <remarks>
109         ''' 当这个函数遇到完全没有重叠的序列片段的时候,是会直接将这个不重叠的片段接到SCS的最末尾的
110         ''' </remarks>
111         <Extension>
112         Public Function ShortestCommonSuperString(Seqs As List(Of String)) As String
113             Dim l As Integer = Seqs.Count
114
115             Do While l > 1
116                 Dim currMax As Integer = Integer.MinValue
117                 Dim finalStr As String = Nothing
118                 Dim p As Integer = -1, q As Integer = -1
119
120                 For j As Integer = 0 To l - 1
121                     For k As Integer = j + 1 To l - 1
122                         Dim str As String = Seqs(j)
123                         Dim b As String = Seqs(k)
124
125                         If str.Contains(b) Then
126                             If b.Length > currMax Then
127                                 finalStr = str
128                                 currMax = b.Length
129                                 p = j
130                                 q = k
131                             End If
132                         ElseIf b.Contains(str) Then
133                             If str.Length > currMax Then
134                                 finalStr = b
135                                 currMax = str.Length
136                                 p = j
137                                 q = k
138                             End If
139                         Else
140                             ' find max common prefix and suffix
141                             Dim maxPrefixMatch = MaxPrefixLength(str, b)
142                             If maxPrefixMatch > currMax Then
143                                 finalStr = str + b.Substring(maxPrefixMatch)
144                                 currMax = maxPrefixMatch
145                                 p = j
146                                 q = k
147                             End If
148
149                             Dim maxSuffixMatch = MaxPrefixLength(b, str)
150                             If maxSuffixMatch > currMax Then
151                                 finalStr = b + str.Substring(maxSuffixMatch)
152                                 currMax = maxSuffixMatch
153                                 p = j
154                                 q = k
155                             End If
156                         End If
157                     Next
158                 Next
159
160                 l -= 1
161                 Seqs(p) = finalStr
162                 Seqs(q) = Seqs(l)
163             Loop
164
165             Return Seqs.First
166         End Function
167
168         Private Function MaxPrefixLength(a As String, b As StringAs Integer
169             Dim max As Integer = 0
170             Dim prefix$
171
172             For i As Integer = 0 To b.Length - 1
173                 prefix = b.Substring(0, i + 1)
174
175                 If a.EndsWith(prefix) Then
176                     max = i + 1
177                 End If
178             Next
179
180             Return max
181         End Function
182     End Module
183 End Namespace