identifier des motifs récurrents/dupliqués en tant que sous-matrices d'un tableau parent

Question

J'ai un problème de recherche de motif typique où je dois identifier où plusieurs motifs apparaissent dans un tableau et les isoler.

ex: ['horse', 'camel', 'horse', 'camel', 'tiger', 'horse', 'camel', 'horse', 'camel']

fonction

doit retourner

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

-à-dire trouver des modèles qui répètent dans un tableau qui peut devenir un sous-réseau,

Ou l'autre façon de définir est - > Trouver tous les sous-tableaux qui se produisent plus de 1 fois dans le tableau principal.

-à-dire des tableaux résultants doivent avoir length > 1 ->

[1, 2, 3, 1, 2, 1, 4, 5] =>[1,2,3] et [1,4,5] les deux sont sous-réseaux, mais [1,2,3] est sous-ensemble récurrents/répétition PAS [1,4,5]

Vous cherchez un algorithme efficace adapté au lieu de solutions en boucle de force brute.

Answer 1

Ce n'est probablement pas ce que vous voulez, mais je ne sais pas ce que vous avez déjà essayé, alors peut-être que cela pourrait être utile. Voici mon approche directe qui tombe probablement sous vos "solutions en boucle de force brute" mais je me suis dit que j'essaierais car personne n'a posté de réponse complète.

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

Sortie:

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

Comme mentionné dans un commentaire que j'ai posté: "serait [camel, horse] inclus dans la sortie"

La sortie que j'ai va avec cela car il y a 2 instances de [camel, horse] aux indices [1-2] et [6-7]. Mais peut-être que je suis complètement mal compris votre question et je ne comprends pas les contraintes. En ce qui concerne l'optimisation, la méthode search(...) par exemple est juste une simple recherche de sous-chaîne, il y a quelques façons plus optimisées de le faire, par exemple. Knuth–Morris–Pratt. Désolé si c'était exactement ce que vous ne vouliez pas, mais peut-être qu'il y a un peu d'utilisation