C#•3d ago

Find all instances of a substring in a string

I would like to try and find all occurrences of a substring in a string without regex, and without looping through the string with IndexOf. Is this possible? Oh don't ask why, it's really an experimental, academic exercise.

7 Replies

jcotton42•3d ago

Should be pretty straightforward. Look for sub[0] at string[x], sub[1] at string[x + 1], etc. If you find a full match, note that. There is a slight detail of whether you count overlapping matches though. eg should AllSubstrings("aaaa", "aa") where is "aa" is the substring return ["aa", "aa"] or ["aa", "aa", "aa"]?

VoidPointerOP•3d ago

I imagined IndexOf would have been more optimized somehow than simple looping. Get the index of the word/substring, then call IndexOf again on the rest of the string after the last occurrence.

jcotton42•3d ago

It would be. It's vectorized if possible.

VoidPointerOP•3d ago

This for an AoC puzzle. I have to find the word XMAS in a large grid of letters, as follows:

This word search allows words to be horizontal, vertical, diagonal, written backwards, or even overlapping other words. It's a little unusual, though, as you don't merely need to find one instance of XMAS - you need to find all of them. Here are a few ways XMAS might appear, where irrelevant characters have been replaced with .:

I thought I'd use IndexOf horizontally, transpose the grid and use IndexOf horizontally again, but effectively for vertical occurences, then only use loops for the diagonals.

jcotton42•3d ago

I need to do last year's AoC. I got a little in, then stopped. I'm thinking - Scan the grid for all the coord pairs that have 'X', stick those in a queue along with the next letter (M) - Run through that queue, looking for the stored next letter (M) in all squares around, then queue those coords along with the next letter (A) - etc. brb, gonna try that

using Candidate = (int R, int C, int DeltaR, int DeltaC, System.ReadOnlyMemory<char> Remainder);

var queue = new Queue<Candidate>();
string[] grid = [
    "XMAS",
    "XMAS",
    "XMAS",
    "XMAS",
    "SAMX"
];

var word = "XMAS";
var count = 0;

var first = word[0];
for (var r = 0; r < grid.Length; r++)
{
    for (var c = 0; c < grid[r].Length; c++)
    {
        if (grid[r][c] == first)
        {
            var remainder = word.AsMemory(1..);
            queue.Enqueue((r, c, -1, -1, remainder));
            queue.Enqueue((r, c, -1, 0, remainder));
            queue.Enqueue((r, c, -1, +1, remainder));

            queue.Enqueue((r, c, 0, -1, remainder));
            queue.Enqueue((r, c, 0, +1, remainder));

            queue.Enqueue((r, c, +1, -1, remainder));
            queue.Enqueue((r, c, +1, 0, remainder));
            queue.Enqueue((r, c, +1, +1, remainder));
        }
    }
}

while (queue.TryDequeue(out var candidate))
{
    var (r, c, dR, dC, remainder) = candidate;
    if (remainder.IsEmpty)
    {
        count++;
        continue;
    }

    var checkR = r + dR;
    var checkC = c + dC;
    if (checkR < 0 || checkC < 0 || checkR >= grid.Length || checkC >= grid[checkR].Length)
    {
        continue;
    }

    if (grid[checkR][checkC] == remainder.Span[0])
    {
        queue.Enqueue((checkR, checkC, dR, dC, remainder[1..]));
    }
}

Console.WriteLine(count);

using Candidate = (int R, int C, int DeltaR, int DeltaC, System.ReadOnlyMemory<char> Remainder);

var queue = new Queue<Candidate>();
string[] grid = [
    "XMAS",
    "XMAS",
    "XMAS",
    "XMAS",
    "SAMX"
];

var word = "XMAS";
var count = 0;

var first = word[0];
for (var r = 0; r < grid.Length; r++)
{
    for (var c = 0; c < grid[r].Length; c++)
    {
        if (grid[r][c] == first)
        {
            var remainder = word.AsMemory(1..);
            queue.Enqueue((r, c, -1, -1, remainder));
            queue.Enqueue((r, c, -1, 0, remainder));
            queue.Enqueue((r, c, -1, +1, remainder));

            queue.Enqueue((r, c, 0, -1, remainder));
            queue.Enqueue((r, c, 0, +1, remainder));

            queue.Enqueue((r, c, +1, -1, remainder));
            queue.Enqueue((r, c, +1, 0, remainder));
            queue.Enqueue((r, c, +1, +1, remainder));
        }
    }
}

while (queue.TryDequeue(out var candidate))
{
    var (r, c, dR, dC, remainder) = candidate;
    if (remainder.IsEmpty)
    {
        count++;
        continue;
    }

    var checkR = r + dR;
    var checkC = c + dC;
    if (checkR < 0 || checkC < 0 || checkR >= grid.Length || checkC >= grid[checkR].Length)
    {
        continue;
    }

    if (grid[checkR][checkC] == remainder.Span[0])
    {
        queue.Enqueue((checkR, checkC, dR, dC, remainder[1..]));
    }
}

Console.WriteLine(count);

so turns out discord's spoiler processing doesn't play well with code blocks?

VoidPointerOP•3d ago

I only wanted to rotate the grid once, to find all vertical instances, after already done horizontal, and then use a loop just for the diagonals. Looks like an interesting approach. I didn't fully grok it just reading it, but I'll play with it, thanks.

jcotton42•2d ago

@VoidPointer I think I goofed on that. Idk why I did the queue thing instead of just... checking in all 8 directions from each instance of word[0]. though, i suppose that's not a goof, just BFS instead DFS

Gaming

Programming

Find all instances of a substring in a string

Did you find this page helpful?