网捷达

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
55
56
57
58
59
60
61
62
///https://cp-algorithms.com/string/z-function.html
///
///Z-function or Z algorithm
///
///Efficient algorithm for pattern occurrence in a string
///
///Time Complexity: O(n) - where n is the length of the string
namespace Algorithms.Strings

module ZFunction =

    let goNext (i, zResult: array<int>, s: string) =
        i + zResult.[i] < s.Length
        && s.[zResult.[i]] = s.[i + zResult.[i]]

    /// <summary>
    /// For the given string this function computes value for each index,
    /// which represents the maximal length substring starting from the index
    /// and is the same as the prefix of the same size
    /// </summary>
    /// <param name="inputString"></param>
    /// <returns></returns>
    let zFunction (inputString: string): list<int> =
        let mutable zResult =
            [| for i in 1 .. inputString.Length -> 0 |]
        // Initialize interval's left pointer and right pointer
        let mutable leftPointer, rightPointer = 0, 0

        for i in 1 .. inputString.Length - 1 do
            // Case when current index is inside the interval
            if i <= rightPointer then
                let minEdge =
                    min (rightPointer - i + 1) (zResult.[i - leftPointer])

                zResult.SetValue(minEdge, i)

            while goNext (i, zResult, inputString) do
                zResult.[i] <- zResult.[i] + 1

            // if new index's result gives us more right interval,
            // we've to update left_pointer and right_pointer
            if i + zResult.[i] - 1 > rightPointer then
                leftPointer <- i
                rightPointer <- i + zResult.[i] - 1

        zResult |> List.ofArray


    let findPattern (pattern: string, inputString: string): int =
        let mutable answer = 0
        // Concatenate 'pattern' and 'input_str' and call z_function
        // with concatenated string
        let zResult = zFunction (pattern + inputString)

        for value in zResult do
            // If value is greater then length of the pattern string
            // that means this index is starting position of substring
            // which is equal to pattern string
            if value >= pattern.Length then
                answer <- answer + 1

        answer