[Scilab-users] Find the position of vector in another vector

[Serge Steer]

One can use the Morris and Pratt algrithme 
(http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/)
I give you a Scilab code of this algorithm. But it should be more 
efficient to add a builtin using the C code given at

http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/pattern.c


Le 22/07/2014 11:38, an.lld a écrit :
> hello scilab users,
>
> i have a problem, i'm trying to find a vector into another vector. my vector
> looks like this:
> A=[7  342  75  36  36  36  9  64  213  82  36  36  36  9  72]
>
> i would like to find the position of the under vector
> B=[36 36 36] in A
> so that i get a vector C=[4 11]... (4 and 11 are the positions where the
> vector B begins).
>
> i have already tried: [v,ka,kb]=intersect(A,B), but this function searches
> only the first occur of "36" in A.
> has somebody  an idea how i can realize that?
>
> sorry, for my bad english.
>
>
>
> --
> View this message in context: http://mailinglists.scilab.org/Find-the-position-of-vector-in-another-vector-tp4030943.html
> Sent from the Scilab users - Mailing Lists Archives mailing list archive at Nabble.com.
> _______________________________________________
> users mailing list
> users at lists.scilab.org
> http://lists.scilab.org/mailman/listinfo/users
>

-------------- next part --------------
function ind=morrisPratt(sequence,pattern)

// Calcul de la fonction de suppléance s
// Pour tout i > 0, s[i] est la longueur bord maximal du 
// préfixe de longueur i du motif, c'est-à-dire p_0 ... p_{i-1}.
// Pour un préfixe w du motif, on a |bord(w)| = s[|w|].
// On a donc |bord^2(w)| = s[|bord(w)|] = s[s[|w|]].
// Les longueurs des bords d'un préfixe w sont donc les valeurs
// s[|w|], s[s[|w|]], s[s[s[|w|]]] ...
  m=length(pattern)
  n=length(sequence)
  ind=[];
  i=-1;
  s(1) = -1;
  for j = 1:m
    while i >= 0 & pattern(i+1) <> pattern(j-1)
      i = s(i+1);
    end
    s(j) = i+1;
  end
  // Recherche du motif
  
  j = 0;
  while j<n 
    i = 0;
    while i < m & j<n
      if pattern(i+1) == sequence(j+1) then
        // Si les deux caractères coïncident, 
        // les deux curseurs avancent d'une position vers la droite.
        j=j+1;
        i=i+1;
      else
        if i==0 then
          j=j+1;
        else
          i = s(i+1);
        end
      end
    end
    if i == m then
      // Occurrence trouvée en position j-i
      ind=[ind j-i+1];
    else
      // Aucune occurrence
      break
    end
  end
endfunction