Task 3 — Match Range Collection

Objective

Create a function that searches one source string for multiple string values.

For every searched value, return all ranges where that value occurs.

The result must use a structured representation.

Input

The source string is:

s1 := "acb abc bcacb cba acba abc bcacb cba acba abc bcacb qwe acb abc bcacb qwe acba"

The search values are:

s2 := []string{
    "cba",
    "acba",
    "bcacb",
    "acb",
}

Result Structure

Define:

type Chain struct {
    ID   string
    List [][]int
}

ID

ID contains the searched string.

For example:

ID: "cba"

List

List contains every match range for that search value.

Every range is represented as:

[]int{
    start,
    end,
}

using the convention:

[start, end)

The start index is inclusive.

The end index is exclusive.

Function

Create:

FindMatch(s1 string, s2 []string)

returning:

[]Chain

Match Range Example

If:

"cba"

begins at index:

14

then its range is:

[14, 17)

because the matched substring contains the source positions:

14
15
16

and index 17 is the first position after the match.

Substring Matching

Search values are treated as substrings.

This means that a value may match both:

a standalone token

and:

part of a larger token

For example:

cba

also occurs inside:

acba

because the characters cba appear consecutively within that value.

Expected Result

For the provided source, the result is:

[]Chain{
    {
        ID: "cba",
        List: [][]int{
            {14, 17},
            {19, 22},
            {33, 36},
            {38, 41},
            {75, 78},
        },
    },
    {
        ID: "acba",
        List: [][]int{
            {18, 22},
            {37, 41},
            {74, 78},
        },
    },
    {
        ID: "bcacb",
        List: [][]int{
            {8, 13},
            {27, 32},
            {46, 51},
            {64, 69},
        },
    },
    {
        ID: "acb",
        List: [][]int{
            {0, 3},
            {10, 13},
            {18, 21},
            {29, 32},
            {37, 40},
            {48, 51},
            {56, 59},
            {66, 69},
            {74, 77},
        },
    },
}

Result Ordering

The returned []Chain should preserve the order of the requested search values.

Given:

[]string{
    "cba",
    "acba",
    "bcacb",
    "acb",
}

the returned chains should appear in the same order.

Within each Chain, match ranges must appear in ascending source-index order.

No Match

If a requested value does not occur, still return a Chain for that search ID.

For example:

Chain{
    ID:   "xyz",
    List: [][]int{},
}

Overlapping Matches

Overlapping matches must be supported.

The scanner should evaluate every valid source position as a possible beginning of a match.

Input Validation

Empty search values should be rejected because their matching behavior is ambiguous.

Corrected Indexing

The original version of this exercise contained example ranges for "cba" that are not consistent with standard indexing of the provided source string.

This revised specification defines one explicit convention:

zero-based indexes
end-exclusive ranges

All expected ranges in this documentation follow that convention.

Restricted Operations

Do not use built-in or standard-library helpers that directly locate substrings.

The matching algorithm must be implemented manually.

Implementation Notes

The search algorithm can be implemented once and reused for every value in s2.

For a match starting at:

start

the end position can be calculated as:

end = start + matchLength