Как найти повторяющиеся шаблоны в массиве символов?

Question

У меня есть массив символов:

a b c x y d e f x y a b c t r e a b c 

Как я могу найти повторяющиеся модели размеров 2 лет?

Массив необходимо пройти от конца. В этом примере мне нужно найти узоры b c, a b, x y и рисунками размеров 3: a b c и x y z. Наряду с индексами соответствия символов.

До сих пор я пытался пройти массив назад и найти шаблоны:

for (int size = 2; size < aLT.size(); size++) { 
    for (int i = aLT.size() - 1; i >= 0; i--) { 
     // code here 
    } 
} 

Answer 1

Это сделает работу, вы можете изменить переменную patternSize на то, что значение, которое вы хотите (ну меньше, чем от размера строка ввода):

Метод String#contains() ищет подпоследовательности первой строки.

public static void main(String[] args) { 
    int patternSize=4; 
    String input = "abcxydefxyabctreabcabcx"; 
    Set<String> patterns = new TreeSet<String>(); 

    // test size n patterns 
    for (int i=0; i<input.length()-patternSize; i++){ 
     String pattern = (String) input.subSequence(i, i+patternSize); 
     String tester=""; 
     if (i>0 && i<input.length()-patternSize-1) 
      tester = input.substring(0,i)+input.substring(i+patternSize); 
     else if (i==0) 
      tester = input.substring(i+patternSize); 
     else if (i==input.length()-patternSize-1) 
      tester = input.substring(0,i); 

     if (tester.contains(pattern)){ 
      patterns.add(pattern); 
     } 
    } 

    System.out.println("Size "+patternSize+" patterns finder"); 
    for(String aPattern : patterns){ 
     System.out.println("The pattern "+aPattern+" was found several times"); 
    } 
} 

Answer 2

int n = 2; // in your case 2 and 3 
Map<String, List<Integer>> matches = new HashMap<String, List<Integer>>(); 
String charsString = new String(chars); 
String current = null; 
String rest = null; 
for(int i = chars.length - n; i >= 0; i--) { 
    current = charsString.substring(i, i + n); 
    rest = charsString.substring(0, i); 
    int index = rest.indexOf(current); 
    if(index > -1) { 
     if(matches.containsKey(current)) { 
      continue; 
     } 
     List<Integer> indices = new ArrayList<Integer>(); 
     indices.add(i); 
     while(index > -1) { 
      indices.add(index); 
      index = rest.indexOf(current, index + 1); 
     } 
     matches.put(current, indices); 
    } 
} 

// print the results 
for(Entry<String, List<Integer>> match : matches.entrySet()) { 
    System.out.println(match.getKey() + " with indices: " + match.getValue()); 
} 

И выход:

ab with indices: [16, 0, 10] 
bc with indices: [17, 1, 11] 
xy with indices: [8, 3] 

Answer 3

Вот метод, который делает то, что вы хотите сделать. Все, что вам нужно сделать, если вы хотите отображать шаблоны разных размеров, если изменить patternSize и строки, которые добавлены в набор. На данный момент я возвращаю счет количества совпадений, но вы можете легко изменить его, чтобы вернуть что-то еще, например индексы, где начинаются совпадения, или логическое значение того, есть ли какие-либо совпадения или нет.

public static int findPatterns(char[] charArray) { 
    int patternSize = 2; 
    Set<String> patterns = new HashSet<>(); 
    patterns.add("bc"); 
    patterns.add("ab"); 
    patterns.add("xy"); 
    int count = 0; 
    if (charArray.length < patternSize) { 
     return 0; 
    } 
    for (int i = 0; i < charArray.length - patternSize + 1; i++) { 
     String pattern = ""; 
     for (int j = i; j < i + patternSize; j++) { 
      pattern += charArray[j]; 
     } 
     if (patterns.contains(pattern)) { 
      count++; 
     } 
    } 
    return count; 
}