Проверьте, существует ли шаблон в строке

Question

Я хотел бы проверить, существует ли шаблон в строке с использованием итерации.

Вот что у меня есть, но в результате я все время становлюсь ложным.

public static void main(String args[]) { 
     String pattern = "abc"; 
     String letters = "abcdef"; 

     char[] patternArray = pattern.toCharArray(); 
     char[] lettersArray = letters.toCharArray(); 

     for(int i = patternArray.length - 1; i<= 2; i++){ 
      for(int j = lettersArray.length - 1; j <= 5;j++){ 
       if(patternArray[i] == lettersArray[j]){ 
        System.out.println("true"); 
       } else{ 
        System.out.println("false"); 
       } 
      } 
     } 
    } 

В основном я хотел бы проверить, если abc существует в строке abcdef

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

Answer 1

Почему бы не так:

public static void main(String args[]) { 
    String pattern = "abc"; 
    String letters = "abcdef"; 

    char[] patternArray = pattern.toCharArray(); 
    char[] lettersArray = letters.toCharArray(); 
    boolean matched = false; 
    for(int i = 0; i< lettersArray.length-patternArray.length && !matched; i++){ 
     for(int j = 0; j < patternArray.length;j++){ 
      if(patternArray[j] == lettersArray[i+j]&&j+1==patternArray.length){ 
       matched = true; 
       System.out.println("true"); 
      } 
      else if(i+1 == lettersArray.length-patternArray.length && j+1 == patternArray.length){ 
       System.out.println("false"); 
     } 
    } 
} 

Answer 2

public static Boolean patternFinder(String str, String pattern){ 
    for (int i = 0; i <= str.length()-pattern.length();i++){ 
     Boolean found = true; 
     for (int f = 0; f < pattern.length();f++){ 
      if (pattern.charAt(f) != str.charAt(i+f)){ 
       found = false; 
       break; 
      } 
     } 
     if (found){ 
      return true; 
     } 
    } 
    return false; 
} 

Это очень простой алгоритм

в основном, вы перебрать строки с начала и проверьте, все буквы в шаблоне равны те, в этом конкретном индексе.

Answer 3

Если вы хотите, чтобы все матчи, я использовать список, чтобы сохранить совпадения адреса в строке.

String pattern = "abc"; 
    String letters = "defabcdefabc"; 
    int i = 0; 
    List<Integer> matches = new ArrayList(); 
    while (i <= letters.length() - pattern.length()) { 
     if (letters.substring(i, i + pattern.length()).equals(pattern)) 
      matches.add(i); 
     i += 1; 
    } 

Вы можете перебирать совпадения, если вы хотите совместить все совпадения с этим решением. Редактировать: язык изменен

Answer 4

Проблема в том, что у вас есть две петли для каждого массива. Здесь вам нужен одиночный цикл для перемещения в обоих массивах с использованием того же индекса.

Answer 5

Вот программа наивной последовательности, которая найдет все совпадения шаблона.

Не рекомендуется для чего-либо практического из-за сложности времени O (mn) (m и n - длины строки поиска и рисунка соответственно).

class Potato 
{ 
    public static void main(String args[]) 
    { 
     char[] search = "flow flow flow over me".toCharArray(); 
     char[] pattern = "flow".toCharArray(); 

     for(int i = 0; i <= search.length - pattern.length; i++) 
      // `-` don't go till the end of the search str. and overflow 
     { 
      boolean flag = true; 
      for(int j=0; j < pattern.length; j++) 
      { 
       if(search[i + j] != pattern[j]) 
       { 
        flag = false; 
        break; 
       } 
      } 
      if (flag) 
       System.out.println("Match found at " + i); 

     } 
    } 
}