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@lists.scilab.org
http://lists.scilab.org/mailman/listinfo/users
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 jn
i = 0;
while i m jn
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
___
users mailing list
users@lists.scilab.org
http://lists.scilab.org/mailman/listinfo/users
