dkh.string

  • SA

    Declaration

    struct SA(T);

    Suffix Array Informations

    • s

      Declaration

      T[] s;

      base string

    • sa

      Declaration

      int[] sa;

      suffix array

    • rsa

      Declaration

      int[] rsa;

      reverse sa, rsa[sa[i]] == i

    • lcp

      Declaration

      int[] lcp;

      lcp

  • Declaration

    SA!T suffixArray(T)(in T[] _s, int B = 200);

    return SA!T. each character must be inside [T(0), T(B)).

    Examples

    1. import std.algorithm : equal, map; string s = "abracadabra"; auto saInfo = s.suffixArray; assert(equal(saInfo.sa.map!(i => s[i..$]), [ "", "a", "abra", "abracadabra", "acadabra", "adabra", "bra", "bracadabra", "cadabra", "dabra", "ra", "racadabra", ]));