Boyer-Moore string search: Difference between revisions
Added FreeBasic
(New post.) |
(Added FreeBasic) |
||
Line 428:
</syntaxhighlight>
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">#define max(a, b) iif((a) > (b), (a), (b))
Dim Shared As Integer suff(), bmBc(), bmGs()
Sub preBmBc(pat As String)
Dim As Integer m = Len(pat), i
Redim bmBc(m)
For i = 1 To m-1
bmBc(Cint(pat[i])) = m - i
Next
End Sub
Sub suffixes(pat As String)
Dim As Integer m = Len(pat), g = m, i, f
Redim suff(m)
suff(m) = m
For i = m-1 To 1 Step -1
If i > g And suff(i + m - f) < i - g Then
suff(i) = suff(i + m - f)
Else
If i < g Then g = i
f = i
While g >= 1 And pat[g] = pat[g + m - f]
g -= 1
Wend
suff(i) = f - g
End If
Next
End Sub
Sub preBmGs(pat As String)
Dim As Integer m = Len(pat), j = 1, i
Redim suff(m)
Redim bmGs(m)
For i = m To 1 Step -1
If suff(i) = i Then
While j < m - i
If bmGs(j) = m Then bmGs(j) = m - i
j += 1
Wend
End If
Next
For i = 1 To m-1
bmGs(m - suff(i)) = m - i
Next
End Sub
Sub BM(pat As String, s As String, case_insensitive As Boolean = False)
Dim As String pins = "'" & pat & "' in " & "'" & s & "'"
If case_insensitive Then
pat = Lcase(pat)
s = Lcase(s)
End If
' Preprocessing
preBmGs(pat)
preBmBc(pat)
' Searching
Dim As Integer j = 0, n = Len(s), m = Len(pat), i = m
While j <= n - m
i -= 1
If pat[i] <> s[i+j] Then Exit While
j += Iif(i < 1, bmGs(0), max(bmGs(i), bmBc(Len(s[i+j]) - m + i)))
Wend
Dim As Integer many = Instr(s, pat)
Dim As String tmp = ""
If Not many > 0 Then
Print "No "; pins
Else
Do While many > 0 'if not found loop will be skipped
tmp &= Str(many) & ","
many = Instr(many + 1, s, pat)
Loop
Print Using "Found & at indices [&]"; pins; tmp & Chr(8)
End If
End Sub
BM("GCAGAGAG","GCATCGCAGAGAGTATACAGTACG")
BM("TCTA","GCTAGCTCTACGAGTCTA")
BM("TAATAAA","GGCTATAATGCGTA")
BM("word","there would have been a time for such a word")
BM("needle","needle need noodle needle")
Const book = "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley" + _
"DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand" + _
"assemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented"
BM("put",book)
BM("and",book)
Const farm = "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with " + _
"bales of all that alfalfa exchanged for milk."
BM("alfalfa",farm)
Sleep</syntaxhighlight>
{{out}}
<pre>Found 'GCAGAGAG' in 'GCATCGCAGAGAGTATACAGTACG' at indices [6]
Found 'TCTA' in 'GCTAGCTCTACGAGTCTA' at indices [7,15]
No 'TAATAAA' in 'GGCTATAATGCGTA'
Found 'word' in 'there would have been a time for such a word' at indices [41]
Found 'needle' in 'needle need noodle needle' at indices [1,20]
Found 'put' in 'InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented' at indices [27,91]
Found 'and' in InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented' at indices [102,129,172]
Found 'alfalfa' in 'Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.' at indices [34,88]</pre>
=={{header|J}}==
| |||