On 5/28/16 6:56 AM, qznc wrote:
The sentinel value is `needleBack+1`, but range elements need not
support addition. Finding a sentinel is hard and most certainly requires
more assumptions about the ranges.
No need for a sentinel really so long as you first search for the last
element of the needle, in the haystack.
Allow me to put on the table a simple brute force routine, specialized
for arrays with copyable elements, no custom predicate etc. Far as I can
tell it does no redundant work:
T[] find(T)(T[] haystack, T[] needle)
{
if (needle.length == 0) return haystack;
immutable lastIndex = needle.length - 1;
auto last = needle[lastIndex];
size_t j = lastIndex;
for (; j < haystack.length; ++j)
{
if (haystack[j] != last) continue;
immutable k = j - lastIndex;
// last elements match
for (size_t i = 0; ; ++i)
{
if (i == lastIndex) return haystack[k .. $];
if (needle[i] != haystack[k + i]) break;
}
}
return haystack[$ .. $];
}
unittest
{
string s1 = "hello abc world";
assert(find(s1, "abc") == "abc world");
assert(find(s1, "def") == "");
}
void main(){}
Andrei
