Check if specific pattern exists in another array and save the index

Question

Let's say I have this pattern and a large array:

String [] pattern = new String[]{"i","am","a", "pattern"};
String [] large_array = new String[]{"not","i","am","a", "pattern","pattern","i","am","a", "pattern", "whatever", "x", "y", i","am","a", "pattern",................, i","am","a", "pattern" ....}; 

As you can see the pattern appears multiple times in the array. The first time at index 1, the second time at index 6, etc... I want to find out at which positions the pattern begins and return it in a collection (eg list).

In this case the position array is 1,6,13, etc...

Here is my current method:

private ArrayList<Integer> getStartPositionOfPattern(String[] headerArray, String[] pattern) {

    ArrayList<Integer> allPositions = new ArrayList<>();
    int idxP = 0, idxH = 0;
    int startPos = 0;
    while (idxH < headerArray.length) {
        if (pattern.length == 1) {
            if (pattern[0].equals(headerArray[idxH])) {
                allPositions.add(idxH);
            }
        } else {
            if (headerArray[idxH].equals(pattern[idxP])) {
                idxP++;
                if (idxP == pattern.length) { //you reached end of pattern
                    idxP = 0; //start Pattern from begining
                    allPositions.add(startPos); //you can save startPosition because pattern is finished
                }
            } else {
                idxP = 0;
                startPos = idxH + 1;
                if (pattern[idxP].equals(headerArray[idxH])) { //if current arrray.idxH is not pattern.idxP but array.idxH is begining of pattern
                    startPos = idxH;
                    idxP++;
                }
            }
        }

        idxH++;

    }
    return allPositions;
}

Is there a way to make my function more readable and faster? I believe it works correctly, but because the function is complex, I worry I might have an undetected bug.

NOTE: headerArray is the large array.

Answer 1

• Prefer returning List to ArrayList. Clients probably don’t need to know the type of list you’re dealing with. Likewise, you can declare your ArrayList as a List, since you don’t use any methods specific to ArrayList. This makes it easier to change your implementation later.

• patternStartIndexes would be a better name than allPositions

• Method variables should be declared on their own lines, and the names should be a lot more descriptive.
• Your while loop might be more clear as a for loop with headerIndex as the loop variable.
• The short-circuit you’re doing for patterns of length one is just noise. It’s a special case that should be correctly handled by the } else { block correctly.
• Your implementation does not do what I would expect for special cases. I’m going to work under the assumption that your implementation is correct. If the pattern is { “a”, “a” } and the header array is { “a”, “a”, “a” }, is the desired output { 0 } or { 0, 1 }? If the latter, you’re going to need a second loop or a somewhat different approach.
• I’m not convinced your comments add much. Non-javadoc comments are typically used to document why, not what. I think your code is pretty straightforward in terms of what it’s doing. You may disagree. :)
• For readability, it’s nice to keep lines relatively short - maybe 120 characters, give or take. People are neither trained for or good at reading very long lines of text.
• You don’t need to track startPosition, which lets us get rid of most of the else block. You can do math: startPosition = headerIndex - patternLength + 1.

If you make all the proposed modifications, your code might look something like:

private List<Integer> getPatternStartIndexes(final String[] headerArray, final String[] pattern) {

    final List<Integer> patternStartIndexes = new ArrayList<>();
    int patternIndex = 0;

    for (int headerIndex = 0; headerIndex < headerArray.length; headerIndex++) {
        if (headerArray[headerIndex].equals(pattern[patternIndex])) {
            patternIndex++;
            if (patternIndex == pattern.length) {
                patternIndex = 0;
                patternStartIndexes.add(headerIndex - pattern.length + 1);
            }
        } else {
            patternIndex = 0;
        }
    }
    return patternStartIndexes;
}

Answer 2

Naming

1. NOTE: headerArray is the large array.

If you need to specify this to us, then your variable name isn't good. We should be able to understand your code with only your code because you wouldn't be beside us when we read it.

2. Don't worry about using full names for your variables. After all, is there a real difference between idxP and indexPosition apart from the fact that it's very clear I'll understand the latter one?

Commenting

Every time you want to write a comment, ask yourself if it is necessary. When you think it is, think again! :p Comments suck (I'm not really talking about XML comments on methods and classes and etc). When you write a comment in a method, it's because there's something weird enough that you'd feel the need to explain why you did something much more than what you did. In your cases, I don't think the comments are necessary.

Readability

In my opinion, there are two great and easy ways to make code more readable.

1. Extracting methods : Taking small chunks of your code that fills a single purpose and make a method out of it.

2. Reduce nesting : Remove as much forking as possible (if, while, for, etc.)

When dealing with algorithms, it's often hard to extract methods as many things are dependent.

However, you have lots of forking, so we can work with that.

if (pattern.length == 1) {
    if (pattern[0].equals(headerArray[idxH])) {
        allPositions.add(idxH);
    }
}

Everytime (exceptions might apply lol) you have two if stuck one to another, they can be merged using the AND (&&) operator.

if (pattern.length == 1 && pattern[0].equals(headerArray[idxH])) {
    allPositions.add(idxH);
}    

Bam, nesting reduced.

You should try to find other ways to reduce nesting, but again, coding complex algorithms often imply spaghetti-ish code. And in this case, you might want to write a meaningful comment as to why your code is this way.

What's next?

If you really want to reach great performance for a "large" array, you might want to consider looking at String searching algorithms. It's not an exact fit to your problem, but there's something to be done.

Small nitpick : Large has a vague definition. If you want to make your code as correct as possible regarding your input, it can be useful to know an approximation of how much data your working with. For you, maybe an array with 100 elements is large, but for some data scientist at IBM, maybe it's 15000000.