Gfyuki

I'm trying to find the index position of the smaller vector inside a bigger one.

I've already solved this problem using strfind and bind2dec,
but I don't want to use strfind, I don't want to convert to string or to deciamls at all.

Given the longer vector

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];

I want to find the index of the smaller vector b inside a

b=[1,1,1,0,0,0];

I would expect to find as result:

result=[15,16,17,18,19,20];

Thank you

Solution with for loops:

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];

b=[1,1,1,0,0,0];

c = ;

b_len = length(b)

maxind0 = length(a) - b_len + 1 %no need to search higher indexes 



for i=1:maxind0

  found = 0;

  for j=1:b_len

    if a(i+j-1) == b(j)

      found = found + 1;

    else

      break;

    end

  end



  if found == b_len  % if sequence is found fill c with indexes

    for j=1:b_len

      c(j)= i+j-1;

    end



    break

  end

end



c %display c

Here is as solution using 1D convolution. It may find multiple matches so start holds beginning indices of sub-vectors:

f = flip(b);



idx = conv(a,f,'same')==sum(b) & conv(~a,~f,'same')==sum(~b);



start = find(idx)-ceil(length(b)/2)+1;



result = start(1):start(1)+length(b)-1;

Does it need to be computationally efficient?

A not very efficient but short solution would be this:

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];;

b=[1,1,1,0,0,0];

where = find(arrayfun(@(n) all(a(n+1:n+length(b))==b),0:length(a)-length(b)));

... gives you 15. Your result would be the vector where:where+length(b)-1.

edit: I tried it and I stand corrected. Here is a version with loops:

function where = find_sequence(a,b)



na = 0;

where = ;

while na < length(a)-length(b)

    c = false;

    for nb = 1:length(b)

        if a(na+nb)~=b(nb)

            na = na + 1;  % + nb

            c = true;                        

            break

        end



    end

    if ~c

        where = [where,na+1];

        na = na + 1;

    end   

end

Despite its loops and their bad reputation in Matlab, it's a lot faster:

a = round(rand(1e6,1));

b = round(rand(10,1));



tic;where1 = find(arrayfun(@(n) all(a(n+1:n+length(b))==b),0:length(a)-length(b)));toc;

tic;where2 = find_sequence(a,b);toc;





>> test_find_sequence

Elapsed time is 4.419223 seconds.

Elapsed time is 0.042969 seconds.

A neater method using for would look like this, there is no need for an inner checking loop as we can vectorize that with all...

a = [1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];

b = [1,1,1,0,0,0];



idx = NaN( size(b) ); % Output NaNs if not found

nb = numel( b );      % Store this for re-use



for ii = 1:numel(a)-nb+1

    if all( a(ii:ii+nb-1) == b )

        % If matched, update the index and exit the loop

        idx = ii:ii+nb-1;

        break

    end

end

Output:

idx = [15,16,17,18,19,20]

Note, I find this a bit easier to read that some of the nested solutions, but it's not necessarily faster, since the comparison is done on all elements in b each time.