fork(1) download
copy 
  1. import std.range: isInputRange, ElementType;
  2. import std.array: array, uninitializedArray, popFront, empty, front;
  3. import std.traits: Unqual, isNarrowString;
  4.  
  5. /**
  6. Range that yields all starting positions of copies of the pattern in
  7. the first Range, using Knuth-Morris-Pratt algorithm. The arguments can
  8. be any ranges, it returns all matches and it scans the first range lazily.
  9. Whenever it yields, it will have read the first range exactly up to
  10. and including the match that caused the yield.
  11. */
  12. struct KMP(R1, R2) if (isInputRange!R1 && isInputRange!R2) {
  13.     // Adapted from lazy KMP Python code by David Eppstein
  14.     // http://c...content-available-to-author-only...e.com/recipes/117214-knuth-morris-pratt-string-matching/
  15.     private R1 items;
  16.     private const Unqual!(ElementType!R2)[] pattern;
  17.     private const size_t[] shifts;
  18.     private size_t startPos;
  19.     private int matchLen;
  20.     private bool is_empty = true;
  21.  
  22.     this(R1 items_, R2 pattern_) /*pure*/ nothrow {
  23.         this.items = items_;
  24.         this.pattern = pattern_.array();
  25.  
  26.         if (this.pattern.length == 0)
  27.             throw new Exception("KMP: pattern can't be empty.");
  28.  
  29.         // build table of shift amounts
  30.         auto table = uninitializedArray!(size_t[])(pattern.length + 1);
  31.         table[] = 1;
  32.         size_t shift = 1;
  33.         foreach (pos; 0 .. pattern.length) {
  34.             while (shift <= pos && pattern[pos] != pattern[pos - shift])
  35.                 shift += table[pos - shift];
  36.             table[pos + 1] = shift;
  37.         }
  38.  
  39.         this.shifts = table;
  40.         popFront(); // search first hit
  41.     }
  42.  
  43.     @property bool empty() const pure nothrow {
  44.         return this.is_empty;
  45.     }
  46.  
  47.     @property size_t front() const pure /*nothrow*/ {
  48.         return startPos;
  49.     }
  50.  
  51.     void popFront() /*pure nothrow*/ {
  52.         this.is_empty = true;
  53.         while (!items.empty) {
  54.             auto it = items.front;
  55.             items.popFront();
  56.             while (matchLen == pattern.length ||
  57.                    matchLen >= 0 &&
  58.                    pattern[matchLen] != it) {
  59.                 startPos += shifts[matchLen];
  60.                 matchLen -= shifts[matchLen];
  61.             }
  62.             matchLen++;
  63.             if (matchLen == pattern.length) {
  64.                 this.is_empty = false;
  65.                 break;
  66.             }
  67.  
  68.         }
  69.     }
  70. }
  71.  
  72.  
  73. KMP!(R1, R2) kmp(R1, R2)(R1 r1, R2 r2) if (isInputRange!R1 && isInputRange!R2) {
  74.     return KMP!(R1, R2)(r1, r2);
  75. }
  76.  
  77. void main() {
  78.     import std.stdio;
  79.  
  80.     //auto kmp0 = KMP!(int[], int[])([], []);
  81.     //writeln(kmp0);
  82.  
  83.     auto kmp1 = KMP!(int[], int[])([], [1]);
  84.     writeln(kmp1);
  85.  
  86.     //auto kmp2 = KMP!(int[], int[])([1], []);
  87.     //writeln(kmp2);
  88.  
  89.     auto kmp3 = KMP!(int[], int[])([1], [1]);
  90.     writeln(kmp3);
  91.  
  92.     auto kmp4 = KMP!(int[], int[])([0,1,2], [0,1,2]);
  93.     writeln(kmp4);
  94.  
  95.     auto kmp5 = KMP!(int[], int[])([0,1,2,3,1,2,3], [1,2,3]);
  96.     writeln(kmp5);
  97.  
  98.     auto kmp6 = KMP!(int[], int[])([1,1], [1]);
  99.     writeln(kmp6);
  100.  
  101.     writeln(KMP!(char[], char[])("redoed".dup, "ed".dup));
  102.     writeln(KMP!(string, string)("redoed", "ed"));
  103.     writeln(KMP!(string, char[])("redoed", "ed".dup));
  104.  
  105.  
  106.     writeln(kmp("redoed".dup, "ed".dup));
  107.     writeln(kmp("redoed", "ed"));
  108.     writeln(kmp("redoed", "ed".dup));
  109.  
  110.     import std.range; // iota, chain
  111.     writeln(kmp(iota(5), iota(3)));
  112.  
  113.     writeln(kmp(chain(iota(5), iota(2), iota(5)), iota(3)));
  114. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dUs5B
language:
D (dmd 2.085.0)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!