# Essays/Non-Overlapping Substrings

`x E. y `finds all occurrences of` x `as a substring in` y` . For example:

x=: 'our' y=: 'fourscore and ten years ago, our fathers' x E. y 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 y ,: ' 1' {~ x E. y fourscore and ten years ago, our fathers 1 1

Substrings can overlap if a non-trivial prefix of` x `occurs as a suffix of` x` .
(A trivial prefix is the empty string or the entire of` x` .)
Suppose only the non-overlapping substrings (NOS) are to be found?
In the following example, the only 1s we want are those at indices` 2 11 24 33 46` .

x=: 'abcabcabc' y=: '--',60$(20$x),'--' (|:":,.i.#y) , y ,: ' 1' {~ x E. y 1111111111222222222233333333334444444444555555555566 01234567890123456789012345678901234567890123456789012345678901 --abcabcabcabcabcabcab--abcabcabcabcabcabcab--abcabcabcabcabca 1 1 1 1 1 1 1 1 1 1 1

Let` s=: x I.@E. y `be the indices of the (possibly overlapping) occurrences
of` x `in` y` .` `If` j `in` s `is the index of an NOS, the index of the next NOS
can be found through the use of the dyad` I. `(interval index).

] s=: x I.@E. y 2 5 8 11 24 27 30 33 46 49 52 ] i=: s I. s+#x 3 4 4 4 7 8 8 8 11 11 11 s ,: i{s,_1 2 5 8 11 24 27 30 33 46 49 52 11 24 24 24 33 46 46 46 _1 _1 _1

If 2 is (the index of) an NOS, then the next NOS is 11; if 5 is an NOS, the next NOS is 24;
if 8 is an NOS, the next NOS is 24; etc.
Since the first element of` s `is the index of an NOS, the indices
of all the NOSes can be found by following the path that starts there; that is,
by computing the transitive closure of that first element.

2 5 8 11 24 27 30 33 46 49 52 _1 11 24 24 24 33 46 46 46 _1 _1 _1 _1

nos=: 4 : 0 s=. x I.@E. y i=. s I. s+#x (i.#y) e. (s,_1) {~ (i,_1) {~^:a: 0 ) y ,: ' 1'{~ x nos y --abcabcabcabcabcabcab--abcabcabcabcabcabcab--abcabcabcabcabca 1 1 1 1 1 t ,: ' 1'{~ 'aaa' nos t=: 59$'a' aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 t ,: ' 1'{~ 'no overlaps' nos t=: 59$'_no overlaps ' _no overlaps _no overlaps _no overlaps _no overlaps _no ove 1 1 1 1

The function can be written tacitly as follows:

tc =: ,&_1 {~^:a: 0: nos1=: i.@#@] e. #@[ (tc@(]I.+) { _1,~]) I.@E.

### See also

Contributed by Roger Hui.