Find index of string in an array of strings where overlap could occur

Question

I am having some trouble writing a variant of sub-string search. Essentially the goal is to write a method that can perform sub-string search except that the source data is in an array of Strings rather the one String.

I have looked around and can't find anyone who has managed to solve this elegantly.

Consider some input data such as:

final List<String> source = new ArrayList<String>();
source.add("abc");
source.add("def");
source.add("ghi");
source.add("jkl");
source.add("mnop");

Now let's say I want to write a method that can return a Pair of the first location of where the target String appears. This Pair represents the first index of the String in the source array where the target appears and its index within that String where the target starts.

Examples with 0 based indices:

subStringArray(source, "def"); //returns Pair(1,0) - 2nd string - 1st index
subStringArray(source, "ef"); //returns Pair(1,1) - 2nd string - 2nd index
subStringArray(source, "fgh"); //returns Pair(1,2) - 2nd string - 3rd index
subStringArray(source, "hijklmno"); //returns Pair(2, 1) - 3rd string - 2nd index
subStringArray(source, "abcf"); //returns null or Pair(-1,-1);

I know it would involve three for loops but I'm not sure how to handle the edge cases, i.e where the target String takes up multiple Strings in the source array.

I should note that I can't allocate more memory.

Answer 1

Hmm, interesting. I think I would opt for a two-pass approach:

First, join all the strings together and check if your pattern exists in the data at all. If it's not found, you don't need to worry about examining the array.

Second, if a match is found, you need to find the array index containing the start of your pattern (if I read your question correctly). There are several ways of going about this. For instance you could shorten your pattern (by gradually clipping the tail end, bisecting it, or something else -- you consider it) until you find a match in an array index. You might even find it's contained entirely within one index, in which case, again, you're done.

If you've found an array index that contains some, but not all, of your pattern, you need to check the next array index (and the next, and the next, if required) until you've matched your entire pattern.

If you get a mismatch during this step, well, you only found a partial match, adn the actual match must be later. In that case, you must consider how much of your just-discarded match you can skip over before you start looking for the new match. For this, look at your pattern: if it contains repetitions ("aaahah!") then you can maybe only skip ahead a single character, but if it's not ("apples") then you can skip as many characters as your pattern is long -- check which array index you can continue looking at.

An alternative method: join the array using a delimiter (so you end up with "abc|def....|mnop) and figure out where to insert delimiter(s) in your target in order to find a match.

A third method: start with the first character of your pattern, and discard all aray indices that don't match it. Add another character from your pattern, and keep going until you've discarded your entire array. Then, go back one step (snip off the last character from your sub-pattern) and you can check the subsequent indices. (This will be slow for long patters.)

...Not that any of this works, either, without additional memory...

Answer 2

For questions like this, it's easier to speak in code. The following code is in C#, but you should be able to adapt it to whatever language you're using.

First, you need a method that can determine if your search candidate matches at a particular location (What you're calling a "pair") in the List of Byte Arrays:

    public bool IsMatch(List<byte[]> haystack, byte[] needle, int x, int y)
    {
        int index = 0; // Needle index

        for (int i = x; i < haystack.Count; i++)
            for (int j = y; j < haystack[i].Length && index < needle.Length; j++)
            {
                if (index >= needle.Length || haystack[i][j] != needle[index])
                    return false;
                y = 0;  // continue search at the beginning of the next byte array
                index++;
            }

        return true;
    }

x and y determine the starting location to begin the matching process (your Pair, essentially). Now you just need to check for a match at every location in the haystack:

    public Tuple<int, int> Search(List<byte[]> haystack, byte[] needle, int x, int y)
    {
        for (int i= x; i<haystack.Count; i++)
            for (int j = y; j < haystack[i].Length; j++)
             {
                if (IsMatch(haystack, needle, i, j))
                    return new Tuple<int, int>(i, j);
                y=0;
             }

        return new Tuple<int, int>(-1, -1); // Not Found.
    }

Call Search() repeatedly with new starting points (based on your previous search result) to get multiple results.

Some tests, to show that it works (you should write more, just to be sure):

    [TestMethod]
    public void Test()
    {
        byte[] needle = new byte[] { (byte)'f', (byte)'g', (byte)'h' };

        var haystack = new List<byte[]>
        {
            new byte[] { (byte)'a', (byte)'b', (byte)'c' },
            new byte[] { (byte)'d', (byte)'e', (byte)'f' },
            new byte[] { (byte)'g', (byte)'h', (byte)'i' },
            new byte[] { (byte)'j', (byte)'k', (byte)'l' },
            new byte[] { (byte)'m', (byte)'n', (byte)'o', (byte)'p' },
         };

        var result1 = IsMatch(haystack, needle, 1, 2 );

        Assert.AreEqual(true, result1);

        var result2 = Search(haystack, needle, 0, 0);
        Assert.AreEqual(1, result2.Item1);
        Assert.AreEqual(2, result2.Item2);
    }