cprint {
  // basically immutable (we make a new copy for every step)
  // to allow evaluating states in parallel and in any order
  sclass GreedySplitIntoWordsCI_Multi {
    S s; // the input to be split
    TreeSet<S> wordsSet = asCISet(words);
    int i = 0, last = 0;
    new ReverseChain<S> out;
      
    // either we return some choices or a final result
    Either<Iterable<GreedySplitIntoWordsCI_Multi>, LS> run() {
      int longestMatch = l(longestPrefixInCISet(substring(s, i), wordsSet));
      if (longestMatch == 0) { // also true when we're at end of string
        flush();
        ret eitherB(out);
      }
        
      ret eitherA(mapNonNulls(countBackwardsTo1(longestMatch), matchLength -> {
        if (!contains(wordsSet, substring(s, i, i+matchLength))) null;
        GreedySplitIntoWordsCI_Multi clone = shallowClone(this);
        clone.i = clone.last = i+longestMatch;
        clone.out = revChainPlus(out, substring(s, i, clone.i));
        ret clone;
      }));
    }
    
    void flush {
      if (i > last) {
        // modifying this object in spite of convention
        out = revChainPlus(out, substring(s, last, i));
        last = i;
      }
    }
  }
}