идентифицировать повторяющиеся/повторяющиеся шаблоны в качестве суб-массивов из родительского массива

Question

У меня есть типичная проблема поиска шаблона, где мне нужно определить, где несколько массивов появляются внутри массива и выделяют их.

например: ['horse', 'camel', 'horse', 'camel', 'tiger', 'horse', 'camel', 'horse', 'camel']

функция должна возвращать

['horse', 'camel'], 
['horse', 'camel', 'horse'], 
['camel', 'horse', 'camel'], 
['horse', 'camel', 'horse', 'camel'] 

т.е. найти закономерности, которые повторяющиеся внутри массива, который может стать суб-массива,

Или другой способ определения является - > Найти все субмассивы, которые встречаются более одного раза в основном массиве.

т.е. полученные массивы должны иметь length > 1 ->

[1, 2, 3, 1, 2, 1, 4, 5] =>[1,2,3] и [1,4,5] оба суб-массивы, но [1,2,3] является повторяющимися/повторяющимися подрешетками НЕ [1,4,5]

В поисках подходящего эффективного алгоритма вместо переборные петлевые решения.

Answer 1

Возможно, это не то, что вы хотите, но я не знаю, что вы пробовали, но, возможно, это может быть полезно. Вот мой прямой подход, который, вероятно, подпадает под ваши «петлевые решения», но я решил попробовать, так как никто не опубликовал полный ответ.

В Java:

// use this to not add duplicates to list 
static boolean contains (List<String[]> patterns, String[] pattern){ 
    for(String[] s: patterns) 
     if (Arrays.equals(pattern,s)) return true; 
    return false; 
} 


/** 
* 
* @param str String array containing all elements in your set 
* @param start index of subarray 
* @param end index of subarray 
* @return if subarray is a recurring pattern 
*/ 
static boolean search (String[] str,int start,int end) { 
    // length of pattern 
    int len = end - start + 1; 

    // how many times you want pattern to 
    // appear in text 
    int n = 1; 

    // increment m if pattern is matched 
    int m = 0; 

    // shift pattern down the array 
    for (int i = end+1; i <= str.length - len; i++) { 
     int j; 
     for (j = 0; j < len; j++) { 
      if (!str[i + j].equals(str[start + j])) 
       break; 
     } 

     // if pattern is matched at [i to i+len] 
     if (j == len) { 
      m++; 
      if (m == n) return true; 
     } 
    } 
    return false; 
} 


/** 
* 
* @param str String array containing all elements in your set 
* @return a list of subsets of input set which are a recurring pattern 
*/ 
static List<String[]> g (String[] str) { 
    // put patterns in here 
    List<String[]> patterns = new ArrayList<>(); 

    // iterate through all possible subarrays in str 
    for(int i = 0; i < str.length-1; i++){ 
     for(int j = i + 1; j < str.length; j++){ 

      // if a pattern is found 
      if (search(str,i,j)) { 
       int len = j-i+1; 
       String[] subarray = new String[len]; 
       System.arraycopy(str,i,subarray,0,len); 
       if (!contains(patterns,subarray)) 
        patterns.add(subarray); 

      } 
     } 
    } 
    return patterns; 
} 

public static void main(String[] args) { 

    String[] str = {"horse", "camel", "horse", "camel", "tiger", 
        "horse", "camel", "horse", "camel"}; 
    // print out 
    List<String[]> patterns = g(str); 
    for (String[] s: patterns) 
     System.out.println(Arrays.toString(s)); 
} 

Выход:

[horse, camel] 
[horse, camel, horse] 
[horse, camel, horse, camel] 
[camel, horse] 
[camel, horse, camel] 

Как уже говорилось в комментарии я разместил: "? Будет [camel, horse] быть включен в выход"

Выход, который у меня есть, имеет 2 экземпляра [camel, horse] по индексам [1-2] и [6-7]. Но, возможно, я полностью не понимаю ваш вопрос, и я не понимаю ограничений.

Что касается оптимизации, то метод search(...), например, представляет собой простой поиск подстроки, есть некоторые более оптимизированные способы выполнения этого, например. Knuth–Morris–Pratt. Извините, если это было именно то, чего вы не хотели, но, возможно, есть какая-то польза