Advertisement
ArXen42

KMP

May 15th, 2016
367
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
VB.NET 5.30 KB | None | 0 0
  1. Imports System.IO
  2. Module Module1
  3.     Private arrPrefix() As Integer
  4.     Private intCounter As Int64 = 0
  5.     Sub Main()
  6.         Dim strInput As String = "This is a KMP substring search algorithm."
  7.         Dim strPattern0 As String = "KMP"
  8.  
  9.         Console.WriteLine(FindSubstring(strInput, strPattern0)) 'Вызов трех алгоритмов поиска нужен для прогрева JIT компилятора
  10.         Console.WriteLine(RabinKarpSearch(strInput, strPattern0))
  11.         Console.WriteLine(SimpleSearch(strInput, strPattern0) - 1)
  12.         Console.WriteLine()
  13.  
  14.         Dim book As String = File.ReadAllText("Солярис.txt") '351231 символ
  15.         Dim output = New List(Of String)
  16.  
  17.         Dim textLength As Integer = 2000
  18.         While (textLength < book.Length)
  19.             Dim currentText As String = book.Substring(0, textLength)
  20.             Dim patternLength As Integer = 1000
  21.             Dim calculationsCount As Integer = 10000
  22.             output.Add(
  23.                 String.Format(
  24.                     "{0}    {1} {2} {3}",
  25.                     textLength,
  26.                     GetAverageTime(AddressOf SimpleSearch, currentText, patternLength, calculationsCount),
  27.                     GetAverageTime(AddressOf RabinKarpSearch, currentText, patternLength, calculationsCount),
  28.                     GetAverageTime(AddressOf FindSubstring, currentText, patternLength, calculationsCount)
  29.                     )
  30.             )
  31.  
  32.             Console.WriteLine(textLength)
  33.  
  34.             textLength += textLength / 32
  35.         End While
  36.  
  37.         File.WriteAllLines("result.txt", output)
  38.     End Sub
  39.  
  40.     Private Function GetAverageTime(searchFunc As Func(Of String, String, Integer), text As String, patternLength As Integer, count As Integer) As Integer
  41.         Dim randomGen = New Random
  42.         Dim timer = New Stopwatch
  43.  
  44.         Dim sum As Long = 0
  45.  
  46.         For i As Integer = 1 To count
  47.             Dim startIndex As Integer = randomGen.Next(0, text.Length - patternLength)
  48.             Dim strPattern As String = text.Substring(startIndex, patternLength)
  49.  
  50.             timer.Reset()
  51.             timer.Start()
  52.             searchFunc(text, strPattern)
  53.             timer.Stop()
  54.  
  55.             sum += timer.ElapsedTicks
  56.         Next
  57.  
  58.         Return sum / count
  59.     End Function
  60.     Private Function GetPrefixFunction(ByVal strPattern As String) As Integer()
  61.         Dim result(strPattern.Length - 1) As Integer
  62.         result(0) = 0
  63.  
  64.         For i As Integer = 1 To strPattern.Length - 1
  65.             Dim k As Integer = result(i - 1)
  66.             While k > 0 AndAlso strPattern(k) <> strPattern(i)
  67.                 k = result(k - 1)
  68.             End While
  69.  
  70.             If strPattern(k) = strPattern(i) Then k += 1
  71.  
  72.             result(i) = k
  73.         Next
  74.  
  75.         Return result
  76.     End Function
  77.  
  78.  
  79.     Public Function FindSubstring(ByVal strInput As String, ByVal strPattern As String) As Integer
  80.         Dim intInputLen As Integer = Len(strInput)
  81.         Dim intPatternLen As Integer = Len(strPattern)
  82.  
  83.         Dim i, j As Integer
  84.         Dim blnFlag As Boolean
  85.  
  86.         If intInputLen = 0 Or intPatternLen = 0 Then Return -2
  87.  
  88.         arrPrefix = GetPrefixFunction(strPattern)
  89.  
  90.         ' j - количество совпавших символов
  91.         j = 0
  92.         ' i - номер сравниваемого очередного символа в входной строке
  93.         For i = 1 To intInputLen
  94.             blnFlag = False
  95.             Do While j > 0 AndAlso GetChar(strPattern, j + 1) <> GetChar(strInput, i)
  96.                 j = arrPrefix(j - 1) 'Не хватало - 1
  97.                 intCounter += 1
  98.                 blnFlag = True
  99.             Loop
  100.             If blnFlag = False Then intCounter += 1
  101.             If GetChar(strPattern, j + 1) = GetChar(strInput, i) Then
  102.                 j += 1
  103.             End If
  104.             If j = intPatternLen Then
  105.                 Return i - intPatternLen
  106.             End If
  107.         Next
  108.  
  109.         Return -1
  110.  
  111.     End Function
  112.  
  113.     Public Function SimpleSearch(ByVal strInput As String, ByVal strPattern As String) As Integer
  114.         Dim intInputLen As Integer = Len(strInput)
  115.         Dim intPatternLen As Integer = Len(strPattern)
  116.         Dim i, j, k As Integer
  117.  
  118.         If intInputLen = 0 Or intPatternLen = 0 Then Return -2
  119.  
  120.         For i = 1 To intInputLen - intPatternLen + 1
  121.             j = 1
  122.             k = i
  123.             Do While GetChar(strPattern, j) = GetChar(strInput, k)
  124.                 j += 1
  125.                 k += 1
  126.                 intCounter += 1
  127.                 If j > intPatternLen Then
  128.                     Return i
  129.                 End If
  130.             Loop
  131.         Next
  132.         Return -1
  133.  
  134.     End Function
  135.  
  136.     Public Function RabinKarpSearch(str As String, seekingStr As String) As Int32 'Из предыдущего задания
  137.         Dim seekingHashCode As Int32 = GetStringHashCode(seekingStr)
  138.         Dim seekingLength As Int32 = seekingStr.Length
  139.  
  140.         Dim firstSubstring As String = str.Substring(0, seekingLength)
  141.  
  142.         Dim previousHashCode As Int32 = GetStringHashCode(firstSubstring) 'Хэш первого образца
  143.  
  144.         If previousHashCode = seekingHashCode Then
  145.             If firstSubstring = seekingStr Then Return 0
  146.         End If
  147.  
  148.         For i As Int32 = 1 To str.Length - seekingStr.Length
  149.             'Рассчет простейшей кольцевой хэш функции
  150.             Dim currentHashCode As Int32 = previousHashCode - AscW(str(i - 1)) + AscW(str(i + seekingLength - 1))
  151.  
  152.             If currentHashCode = seekingHashCode Then 'Если совпадает, то посимвольное сравнение
  153.                 Dim success As Boolean = True
  154.                 For j As Int32 = 0 To seekingLength - 1
  155.                     If str(i + j) <> seekingStr(j) Then
  156.                         success = False
  157.                         Exit For
  158.                     End If
  159.                 Next
  160.  
  161.                 If (success) Then Return i
  162.             End If
  163.  
  164.             previousHashCode = currentHashCode
  165.         Next
  166.  
  167.         Return -1
  168.     End Function
  169.  
  170.     Private Function GetStringHashCode(str As String) As Int32
  171.         Dim hashCode As Int32 = 0
  172.         For i As Int32 = 0 To str.Length - 1
  173.             hashCode += AscW(str(i))
  174.         Next
  175.  
  176.         Return hashCode
  177.     End Function
  178. End Module
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement