import std.range: isInputRange, ElementType;
import std.array: array, uninitializedArray, popFront, empty, front;
import std.traits: Unqual, isNarrowString;
/**
Range that yields all starting positions of copies of the pattern in
the first Range, using Knuth-Morris-Pratt algorithm. The arguments can
be any ranges, it returns all matches and it scans the first range lazily.
Whenever it yields, it will have read the first range exactly up to
and including the match that caused the yield.
*/
struct KMP(R1, R2) if (isInputRange!R1 && isInputRange!R2) {
// Adapted from lazy KMP Python code by David Eppstein
// http://c...content-available-to-author-only...e.com/recipes/117214-knuth-morris-pratt-string-matching/
private R1 items;
private const Unqual!(ElementType!R2)[] pattern;
private const size_t[] shifts;
private size_t startPos;
private int matchLen;
private bool is_empty = true;
this(R1 items_, R2 pattern_) /*pure*/ nothrow {
this.items = items_;
this.pattern = pattern_.array();
if (this.pattern.length == 0)
throw new Exception("KMP: pattern can't be empty.");
// build table of shift amounts
auto table = uninitializedArray!(size_t[])(pattern.length + 1);
table[] = 1;
size_t shift = 1;
foreach (pos; 0 .. pattern.length) {
while (shift <= pos && pattern[pos] != pattern[pos - shift])
shift += table[pos - shift];
table[pos + 1] = shift;
}
this.shifts = table;
popFront(); // search first hit
}
@property bool empty() const pure nothrow {
return this.is_empty;
}
@property size_t front() const pure /*nothrow*/ {
return startPos;
}
void popFront() /*pure nothrow*/ {
this.is_empty = true;
while (!items.empty) {
auto it = items.front;
items.popFront();
while (matchLen == pattern.length ||
matchLen >= 0 &&
pattern[matchLen] != it) {
startPos += shifts[matchLen];
matchLen -= shifts[matchLen];
}
matchLen++;
if (matchLen == pattern.length) {
this.is_empty = false;
break;
}
}
}
}
KMP!(R1, R2) kmp(R1, R2)(R1 r1, R2 r2) if (isInputRange!R1 && isInputRange!R2) {
return KMP!(R1, R2)(r1, r2);
}
void main() {
import std.stdio;
//auto kmp0 = KMP!(int[], int[])([], []);
//writeln(kmp0);
auto kmp1 = KMP!(int[], int[])([], [1]);
writeln(kmp1);
//auto kmp2 = KMP!(int[], int[])([1], []);
//writeln(kmp2);
auto kmp3 = KMP!(int[], int[])([1], [1]);
writeln(kmp3);
auto kmp4 = KMP!(int[], int[])([0,1,2], [0,1,2]);
writeln(kmp4);
auto kmp5 = KMP!(int[], int[])([0,1,2,3,1,2,3], [1,2,3]);
writeln(kmp5);
auto kmp6 = KMP!(int[], int[])([1,1], [1]);
writeln(kmp6);
writeln(KMP!(char[], char[])("redoed".dup, "ed".dup));
writeln(KMP!(string, string)("redoed", "ed"));
writeln(KMP!(string, char[])("redoed", "ed".dup));
writeln(kmp("redoed".dup, "ed".dup));
writeln(kmp("redoed", "ed"));
writeln(kmp("redoed", "ed".dup));
import std.range; // iota, chain
writeln(kmp(iota(5), iota(3)));
writeln(kmp(chain(iota(5), iota(2), iota(5)), iota(3)));
}
aW1wb3J0IHN0ZC5yYW5nZTogaXNJbnB1dFJhbmdlLCBFbGVtZW50VHlwZTsKaW1wb3J0IHN0ZC5hcnJheTogYXJyYXksIHVuaW5pdGlhbGl6ZWRBcnJheSwgcG9wRnJvbnQsIGVtcHR5LCBmcm9udDsKaW1wb3J0IHN0ZC50cmFpdHM6IFVucXVhbCwgaXNOYXJyb3dTdHJpbmc7CgovKioKUmFuZ2UgdGhhdCB5aWVsZHMgYWxsIHN0YXJ0aW5nIHBvc2l0aW9ucyBvZiBjb3BpZXMgb2YgdGhlIHBhdHRlcm4gaW4KdGhlIGZpcnN0IFJhbmdlLCB1c2luZyBLbnV0aC1Nb3JyaXMtUHJhdHQgYWxnb3JpdGhtLiBUaGUgYXJndW1lbnRzIGNhbgpiZSBhbnkgcmFuZ2VzLCBpdCByZXR1cm5zIGFsbCBtYXRjaGVzIGFuZCBpdCBzY2FucyB0aGUgZmlyc3QgcmFuZ2UgbGF6aWx5LgpXaGVuZXZlciBpdCB5aWVsZHMsIGl0IHdpbGwgaGF2ZSByZWFkIHRoZSBmaXJzdCByYW5nZSBleGFjdGx5IHVwIHRvCmFuZCBpbmNsdWRpbmcgdGhlIG1hdGNoIHRoYXQgY2F1c2VkIHRoZSB5aWVsZC4KKi8Kc3RydWN0IEtNUChSMSwgUjIpIGlmIChpc0lucHV0UmFuZ2UhUjEgJiYgaXNJbnB1dFJhbmdlIVIyKSB7CiAgICAvLyBBZGFwdGVkIGZyb20gbGF6eSBLTVAgUHl0aG9uIGNvZGUgYnkgRGF2aWQgRXBwc3RlaW4KICAgIC8vIGh0dHA6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS9yZWNpcGVzLzExNzIxNC1rbnV0aC1tb3JyaXMtcHJhdHQtc3RyaW5nLW1hdGNoaW5nLwogICAgcHJpdmF0ZSBSMSBpdGVtczsKICAgIHByaXZhdGUgY29uc3QgVW5xdWFsIShFbGVtZW50VHlwZSFSMilbXSBwYXR0ZXJuOwogICAgcHJpdmF0ZSBjb25zdCBzaXplX3RbXSBzaGlmdHM7CiAgICBwcml2YXRlIHNpemVfdCBzdGFydFBvczsKICAgIHByaXZhdGUgaW50IG1hdGNoTGVuOwogICAgcHJpdmF0ZSBib29sIGlzX2VtcHR5ID0gdHJ1ZTsKCiAgICB0aGlzKFIxIGl0ZW1zXywgUjIgcGF0dGVybl8pIC8qcHVyZSovIG5vdGhyb3cgewogICAgICAgIHRoaXMuaXRlbXMgPSBpdGVtc187CiAgICAgICAgdGhpcy5wYXR0ZXJuID0gcGF0dGVybl8uYXJyYXkoKTsKCiAgICAgICAgaWYgKHRoaXMucGF0dGVybi5sZW5ndGggPT0gMCkKICAgICAgICAgICAgdGhyb3cgbmV3IEV4Y2VwdGlvbigiS01QOiBwYXR0ZXJuIGNhbid0IGJlIGVtcHR5LiIpOwoKICAgICAgICAvLyBidWlsZCB0YWJsZSBvZiBzaGlmdCBhbW91bnRzCiAgICAgICAgYXV0byB0YWJsZSA9IHVuaW5pdGlhbGl6ZWRBcnJheSEoc2l6ZV90W10pKHBhdHRlcm4ubGVuZ3RoICsgMSk7CiAgICAgICAgdGFibGVbXSA9IDE7CiAgICAgICAgc2l6ZV90IHNoaWZ0ID0gMTsKICAgICAgICBmb3JlYWNoIChwb3M7IDAgLi4gcGF0dGVybi5sZW5ndGgpIHsKICAgICAgICAgICAgd2hpbGUgKHNoaWZ0IDw9IHBvcyAmJiBwYXR0ZXJuW3Bvc10gIT0gcGF0dGVybltwb3MgLSBzaGlmdF0pCiAgICAgICAgICAgICAgICBzaGlmdCArPSB0YWJsZVtwb3MgLSBzaGlmdF07CiAgICAgICAgICAgIHRhYmxlW3BvcyArIDFdID0gc2hpZnQ7CiAgICAgICAgfQoKICAgICAgICB0aGlzLnNoaWZ0cyA9IHRhYmxlOwogICAgICAgIHBvcEZyb250KCk7IC8vIHNlYXJjaCBmaXJzdCBoaXQKICAgIH0KCiAgICBAcHJvcGVydHkgYm9vbCBlbXB0eSgpIGNvbnN0IHB1cmUgbm90aHJvdyB7CiAgICAgICAgcmV0dXJuIHRoaXMuaXNfZW1wdHk7CiAgICB9CgogICAgQHByb3BlcnR5IHNpemVfdCBmcm9udCgpIGNvbnN0IHB1cmUgLypub3Rocm93Ki8gewogICAgICAgIHJldHVybiBzdGFydFBvczsKICAgIH0KCiAgICB2b2lkIHBvcEZyb250KCkgLypwdXJlIG5vdGhyb3cqLyB7CiAgICAgICAgdGhpcy5pc19lbXB0eSA9IHRydWU7CiAgICAgICAgd2hpbGUgKCFpdGVtcy5lbXB0eSkgewogICAgICAgICAgICBhdXRvIGl0ID0gaXRlbXMuZnJvbnQ7CiAgICAgICAgICAgIGl0ZW1zLnBvcEZyb250KCk7CiAgICAgICAgICAgIHdoaWxlIChtYXRjaExlbiA9PSBwYXR0ZXJuLmxlbmd0aCB8fAogICAgICAgICAgICAgICAgICAgbWF0Y2hMZW4gPj0gMCAmJgogICAgICAgICAgICAgICAgICAgcGF0dGVyblttYXRjaExlbl0gIT0gaXQpIHsKICAgICAgICAgICAgICAgIHN0YXJ0UG9zICs9IHNoaWZ0c1ttYXRjaExlbl07CiAgICAgICAgICAgICAgICBtYXRjaExlbiAtPSBzaGlmdHNbbWF0Y2hMZW5dOwogICAgICAgICAgICB9CiAgICAgICAgICAgIG1hdGNoTGVuKys7CiAgICAgICAgICAgIGlmIChtYXRjaExlbiA9PSBwYXR0ZXJuLmxlbmd0aCkgewogICAgICAgICAgICAgICAgdGhpcy5pc19lbXB0eSA9IGZhbHNlOwogICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgfQp9CgoKS01QIShSMSwgUjIpIGttcChSMSwgUjIpKFIxIHIxLCBSMiByMikgaWYgKGlzSW5wdXRSYW5nZSFSMSAmJiBpc0lucHV0UmFuZ2UhUjIpIHsKICAgIHJldHVybiBLTVAhKFIxLCBSMikocjEsIHIyKTsKfQoKdm9pZCBtYWluKCkgewogICAgaW1wb3J0IHN0ZC5zdGRpbzsKCiAgICAvL2F1dG8ga21wMCA9IEtNUCEoaW50W10sIGludFtdKShbXSwgW10pOwogICAgLy93cml0ZWxuKGttcDApOwoKICAgIGF1dG8ga21wMSA9IEtNUCEoaW50W10sIGludFtdKShbXSwgWzFdKTsKICAgIHdyaXRlbG4oa21wMSk7CgogICAgLy9hdXRvIGttcDIgPSBLTVAhKGludFtdLCBpbnRbXSkoWzFdLCBbXSk7CiAgICAvL3dyaXRlbG4oa21wMik7CgogICAgYXV0byBrbXAzID0gS01QIShpbnRbXSwgaW50W10pKFsxXSwgWzFdKTsKICAgIHdyaXRlbG4oa21wMyk7CgogICAgYXV0byBrbXA0ID0gS01QIShpbnRbXSwgaW50W10pKFswLDEsMl0sIFswLDEsMl0pOwogICAgd3JpdGVsbihrbXA0KTsKCiAgICBhdXRvIGttcDUgPSBLTVAhKGludFtdLCBpbnRbXSkoWzAsMSwyLDMsMSwyLDNdLCBbMSwyLDNdKTsKICAgIHdyaXRlbG4oa21wNSk7CgogICAgYXV0byBrbXA2ID0gS01QIShpbnRbXSwgaW50W10pKFsxLDFdLCBbMV0pOwogICAgd3JpdGVsbihrbXA2KTsKCiAgICB3cml0ZWxuKEtNUCEoY2hhcltdLCBjaGFyW10pKCJyZWRvZWQiLmR1cCwgImVkIi5kdXApKTsKICAgIHdyaXRlbG4oS01QIShzdHJpbmcsIHN0cmluZykoInJlZG9lZCIsICJlZCIpKTsKICAgIHdyaXRlbG4oS01QIShzdHJpbmcsIGNoYXJbXSkoInJlZG9lZCIsICJlZCIuZHVwKSk7CgoKICAgIHdyaXRlbG4oa21wKCJyZWRvZWQiLmR1cCwgImVkIi5kdXApKTsKICAgIHdyaXRlbG4oa21wKCJyZWRvZWQiLCAiZWQiKSk7CiAgICB3cml0ZWxuKGttcCgicmVkb2VkIiwgImVkIi5kdXApKTsKCiAgICBpbXBvcnQgc3RkLnJhbmdlOyAvLyBpb3RhLCBjaGFpbgogICAgd3JpdGVsbihrbXAoaW90YSg1KSwgaW90YSgzKSkpOwoKICAgIHdyaXRlbG4oa21wKGNoYWluKGlvdGEoNSksIGlvdGEoMiksIGlvdGEoNSkpLCBpb3RhKDMpKSk7Cn0=