octave_packages/m/strings/findstr.m

   1 ## Copyright (C) 1996-2012 Kurt Hornik
   2 ##
   3 ## This file is part of Octave.
   4 ##
   5 ## Octave is free software; you can redistribute it and/or modify it
   6 ## under the terms of the GNU General Public License as published by
   7 ## the Free Software Foundation; either version 3 of the License, or (at
   8 ## your option) any later version.
   9 ##
  10 ## Octave is distributed in the hope that it will be useful, but
  11 ## WITHOUT ANY WARRANTY; without even the implied warranty of
  12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 ## General Public License for more details.
  14 ##
  15 ## You should have received a copy of the GNU General Public License
  16 ## along with Octave; see the file COPYING.  If not, see
  17 ## <http://www.gnu.org/licenses/>.
  18
  19 ## -*- texinfo -*-
  20 ## @deftypefn  {Function File} {} findstr (@var{s}, @var{t})
  21 ## @deftypefnx {Function File} {} findstr (@var{s}, @var{t}, @var{overlap})
  22 ## Return the vector of all positions in the longer of the two strings
  23 ## @var{s} and @var{t} where an occurrence of the shorter of the two starts.
  24 ## If the optional argument @var{overlap} is true, the returned vector
  25 ## can include overlapping positions (this is the default).  For example:
  26 ##
  27 ## @example
  28 ## @group
  29 ## findstr ("ababab", "a")
  30 ##      @result{} [1, 3, 5];
  31 ## findstr ("abababa", "aba", 0)
  32 ##      @result{} [1, 5]
  33 ## @end group
  34 ## @end example
  35 ##
  36 ## @strong{Caution:} @code{findstr} is scheduled for deprecation.  Use
  37 ## @code{strfind} in all new code.
  38 ## @seealso{strfind, strmatch, strcmp, strncmp, strcmpi, strncmpi, find}
  39 ## @end deftypefn
  40
  41 ## Note that this implementation swaps the strings if second one is longer
  42 ## than the first, so try to put the longer one first.
  43 ##
  44 ## Author: Kurt Hornik <Kurt.Hornik@wu-wien.ac.at>
  45 ## Adapted-By: jwe
  46
  47 function v = findstr (s, t, overlap = true)
  48
  49   if (nargin < 2 || nargin > 3)
  50     print_usage ();
  51   endif
  52
  53   if (all (size (s) > 1) || all (size (t) > 1))
  54     error ("findstr: arguments must have only one non-singleton dimension");
  55   endif
  56
  57   ## Make S be the longer string.
  58   if (length (s) < length (t))
  59     [s, t] = deal (t, s);
  60   endif
  61
  62   l_s = length (s);
  63   l_t = length (t);
  64
  65   if (l_t == 0)
  66     ## zero length target: return empty set
  67     v = [];
  68
  69   elseif (l_t == 1)
  70     ## length one target: simple find
  71     v = find (s == t);
  72
  73   elseif (l_t == 2)
  74     ## length two target: find first at i and second at i+1
  75     v = find (s(1:l_s-1) == t(1) & s(2:l_s) == t(2));
  76
  77   else
  78     ## length three or more: match the first three by find then go through
  79     ## the much smaller list to determine which of them are real matches
  80     limit = l_s - l_t + 1;
  81     v = find (s(1:limit) == t(1)
  82               & s(2:limit+1) == t(2)
  83               & s (3:limit+2) == t(3));
  84   endif
  85
  86   ## Need to search the index vector if our find was too short
  87   ## (target length > 3), or if we don't allow overlaps.  Note though
  88   ## that there cannot be any overlaps if the first character in the
  89   ## target is different from the remaining characters in the target,
  90   ## so a single character, two different characters, or first character
  91   ## different from the second two don't need to be searched.
  92   if (l_t >= 3 || (! overlap && l_t > 1 && any (t(1) == t(2:l_t))))
  93     ## force strings to be both row vectors or both column vectors
  94     if (all (size (s) != size (t)))
  95       t = t.';
  96     endif
  97
  98     ## determine which ones to keep
  99     keep = zeros (size (v));
 100     ind = 0:l_t-1;
 101     if (overlap)
 102       for idx = 1:length (v)
 103         keep(idx) = all (s(v(idx) + ind) == t);
 104       endfor
 105     else
 106       ## First possible position for next non-overlapping match.
 107       next = 1;
 108       for idx = 1:length (v)
 109         if (v(idx) >= next && s(v(idx) + ind) == t)
 110           keep(idx) = 1;
 111           ## Skip to the next possible match position.
 112           next = v(idx) + l_t;
 113         else
 114           keep(idx) = 0;
 115         endif
 116       endfor
 117     endif
 118     if (! isempty (v))
 119       v = v(find (keep));
 120     endif
 121   endif
 122
 123   if (isempty (v))
 124     v = [];
 125   endif
 126
 127   ## Always return a row vector, because that's what the old one did.
 128   if (iscolumn (v))
 129     v = v.';
 130   endif
 131
 132 endfunction
 133
 134
 135 %!assert (findstr ("abababa", "a"), [1, 3, 5, 7])
 136 %!assert (findstr ("abababa", "aba"), [1, 3, 5]);
 137 %!assert (findstr ("aba", "abababa", 0), [1, 5]);
 138
 139 %% Test input validation
 140 %!error findstr ()
 141 %!error findstr ("foo", "bar", 3, 4);
 142 %!error findstr (["AB" ; "CD"], "C");
 143