Brute force pattern search java

Question

I have been trying to write a substring search method that gets the count of the number of patterns that show up in a string. My question has to deal with the logic of the multiple for loops that I have and the if statements. If the input string is AABABAA and the input pattern is AA it should iterate through and return count of 2. Any suggestions to help me finish my code?

public int getCount(String pattern){

for (int i=0; i< this.strand.length()-pattern.length(); i++){
    for (int k=0; k<pattern.length(); k++){
        if (this.strand.charAt(i) == pattern.charAt(k)){
                for(int j=1; j<pattern.length()-1; j++){
                    if (this.strand.charAt(j+i) == pattern.charAt(j)){
                        if(j==pattern.length()){
                            Count++;
                        }
                }
                    else{
                        break;
                    }
                }
        }

        else if (this.strand.charAt(i)!=pattern.charAt(k)){
            break;
        }
    }
}
        return Count;
    }

I'm curious why you're needing three for-loops. If I'm reading your question correctly, it can be done with one. — Chris Forrence, Jan 30 '14 at 23:33
@ChrisForrence If he can't use `substring` or compare strings, then I think he needs two loops unless he sets up a [DFA](http://en.wikipedia.org/wiki/Deterministic_finite_automaton) first ... or does something tricky with his indexes. — ajb, Jan 30 '14 at 23:37
i dont want to use substrings because i eventually have to use other wildcard variables so for now just for loops — user2876613, Jan 30 '14 at 23:46

martijnn2008 · Accepted Answer · 2015-10-23T09:56:06.820

1

Something like this? If you don't want to use .subString(int, int)

public static int findSubString(String input, String pattern) {
    int output = 0;
    for (int i = 0; i <= input.length() - pattern.length(); i++) {
        boolean ok = true;
        for (int k = 0; k < pattern.length(); k++) {
            if(input.charAt(i + k) != pattern.charAt(k)) {
                ok = false;
                break;
            }
        }
        if(ok) output++;
    }
    return output;
}

I think this would also work if the length of pattern is larger then the length of input. I use break; because you already found a mismatch, so it would be a waste of time to do any further checks.

edited Oct 23 '15 at 09:56

answered Jan 30 '14 at 23:37

martijnn2008

3,552
5
30
40

this looks like what I want to do, ill give it a try – user2876613 Jan 30 '14 at 23:54
looks like your outer for loop comparison is not right. – SonalKhodiyar Oct 18 '15 at 17:08
@SonalKhodiyar I have fixed it, sorry for any inconvenience. – martijnn2008 Oct 20 '15 at 17:23

score 0 · Answer 2 · edited May 23 '17 at 12:30

I know this completely disregards the logic of your loops, but if there's nothing preventing it, why don't you use regular expressions instead?

Something like this works. Be sure to import java.util.regex.*

calling getCount("AABABAA","AA") returns 2

public int getCount(String input, String expression) {
    Pattern pattern = Pattern.compile(expression);
    Matcher matcher = pattern.matcher(input);

    int count = 0;
    while (matcher.find())
        count++;

    return count;
}

Note, depending on what your expression is, you may need to escape it. Start with this question, if so: How to escape text for regular expression in Java

score 0 · Answer 3 · answered Jan 30 '14 at 23:41

This will keep you at one for-loop, as well as sanity-check pattern and this.strand.

public int getCount(String pattern) {
    int count = 0;

    // Sanity check; make sure neither pattern nor strand are null
    if(pattern == null
            || this.strand == null
            || pattern.length() > this.strand.length()) {
        return count;
    }

    String _substring;
    for(int i = 0; i <= this.strand.length() - pattern.length(); i++) {
        _substring = this.strand.substring(i, i + pattern.length());
        if(_substring.equals(pattern)) {
            count++;
        }
    }
    return count;
}

score 0 · Answer 4 · answered Nov 19 '15 at 00:58

import java.util.Scanner;


public class StringMatch1 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner in = new Scanner(System.in);
        String T, P, sub;

        System.out.print("Enter a text string T: ");
         T = in.nextLine();
         System.out.print("Enter a pattern string P: ");
         P = in.next();

         for (int i = 0; i <= T.length() - P.length(); i++ ){

             sub = T.substring(i, i + P.length()); // try to match this

             if (P.equals(sub)){
                 System.out.println("Found pattern at position " + i);
             }
         }


     }

}

Brute force pattern search java

4 Answers4