-2

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.

  • 1
    You can't do it without allocating more memory. You'll need memory to track the boundaries anyway. You can't tell if there's a performance problem until you measure. I suspect that it's going to perform faster if you're willing to allocate one string for the search. Do you want that code? – Robert Harvey Oct 20 '15 at 18:18
  • 2
    I guess you'd better edit your question to use byte arrays for the example instead of strings. Otherwise we'll all be spinning our wheels manipulating strings, which is not going to serve your purpose. – Robert Harvey Oct 20 '15 at 18:27
  • 3
    Describe the actual problem you are having. Indicate that each of these is a very long array of bytes that you are reading in as part of a stream. You've got a stream coming - so things are happening about you discarding old data (this isn't a static array list that you can massage all day long). – user40980 Oct 20 '15 at 18:32
  • 1
    I understand these criticisms and it was my mistake not to provide more detail. I was trying to generalize my problem. Essentially, without getting into too much details, I have an array of large byte arrays. I am given a target byte array and I need to find where this target array occurs. Everything is in memory. Should I modify this post entirely or create a new one? – AbuZubair Oct 20 '15 at 18:42
  • 2
    Just modify this post so it explains your problem accurately. – KlaymenDK Oct 20 '15 at 19:13
0

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...

0

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);
    }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.