Brute force pattern search java

Question

Я пытаюсь написать метод поиска подстроки, который получает количество числа шаблонов, отображаемых в строке. Мой вопрос должен иметь дело с логикой множества для циклов, которые у меня есть, и операторов if. Если входная строка AABABAA, а шаблон ввода - AA, он должен перебирать и возвращать счет 2. Любые предложения, которые помогут мне закончить мой код?

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

Answer 1

Что-то вроде этого? Если вы не хотите использовать .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; 
} 

Я думаю, что это также будет работать, если длина pattern больше чем длина input. Я использую break;, потому что вы уже нашли несоответствие, так что было бы пустой тратой времени на дальнейшие проверки.

Answer 2

Я знаю, что это полностью игнорирует логику ваших циклов, но если ничего не мешает, почему бы вам не использовать регулярные выражения?

Нечто подобное работает. Обязательно импортировать java.util.regex.*

getCount("AABABAA","AA") вызова возвращается 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; 
} 

Обратите внимание, в зависимости от того, что ваше выражение, вам может понадобиться, чтобы избежать его. Начните с этого вопроса, если да: How to escape text for regular expression in Java

Answer 3

Это будет держать вас за один цикл, а также проверку работоспособности pattern и 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; 
} 

Answer 4

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


    } 

}