[Jprogramming] split a string with a delimiter word

[Roger Hui]

Alternatively:

   tc =: 3 : '{&(y.,_1)^:a: 0'
   nos=: i.@#@] e. #@[ (tc@(]I.+) { _1,~]) I. at E.

And for you tacit and/or one-liner fans:

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

tc denotes transitive closure; nos denotes non-overlapping substring.



----- Original Message ----- 
From: "Roger Hui" <RHui000 at shaw.ca>
To: "Programming forum" <programming at jsoftware.com>
Sent: Monday, January 09, 2006 4:50 PM
Subject: Re: [Jprogramming] split a string with a delimiter word

intx is almost exactly the dyad I. (new to J 6.01).  Thus:

nos=: 4 : 0
 s=. x. I. at E. y.
 i=. s I. s+#x.
 (i.#y.) e. (s,_1) {~ {&(i,_1)^:a: 0
)



----- Original Message ----- 
From: "Roger Hui" <RHui000 at shaw.ca>
To: "Programming forum" <programming at jsoftware.com>
Sent: Monday, January 09, 2006 1:46 PM
Subject: Re: [Jprogramming] split a string with a delimiter word

The non-overlapping substring (nos) problem can be solved as follows.
The ideas were first described in my APL87 paper, "Some Uses of 
{ and }", section 1.2.  The key is the use of transitive closure.

First, a subfunction that computes the "interval index".

intx=: #@[ ([ }. +/\@:> /: ]) /:@,

The left argument is a non-decreasing vector x that partitions
the real numbers into contiguous intervals; intx computes the index 
of the interval that contains list y .  That is, if z=: x intx y , 
then ($z)-:$y and i{z is the least non-negative integer such that 
(i{y)<(i{z){x .  For example:

   ] x=: +/\ 10 ?.@$ 10
6 11 20 22 26 35 35 42 42 46
   x intx 0
0
   x intx 5
0
   x intx 6
1
   x intx 12
2
   x intx 47
10
   x intx 0 5 6 12 47 11 21
0 0 1 2 10 2 3

Now consider the problem of finding non-overlapping occurrences
of x in y , where:

   x=: 'abcabcabc'
   ] y=: 80$(20$x),'--'
   y
abcabcabcabcabcabcab--abcabcabcabcabcabcab--abcabcabcabcabcabcab--abcabcabcabcab

Start with the indices produced by the dyad E. :

   ] s=: x I. at E. y
0 3 6 9 22 25 28 31 44 47 50 53 66 69

These contain indices of overlapping substrings.  The question to ask is:
for each index j in s, if j is a non-overlapping substring, what would
be index of the next non-overlapping substring?  The question can be
answered through the use of intx and transitive closure:

   ] i=: s intx s+<:#x.
3 4 4 4 7 8 8 8 11 12 12 12 14 14
   s ,: i{s,_1
0  3  6  9 22 25 28 31 44 47 50 53 66 69
9 22 22 22 31 44 44 44 53 66 66 66 _1 _1
   (s,_1) {~ {&(i,_1)^:a: 0
0 9 22 31 44 53 66 _1 _1

nos=: 4 : 0
 s=. x. I. at E. y.
 i=. s intx s+<:#x.
 (i.#y.) e. (s,_1) {~ {&(i,_1)^:a: 0
)

   x nos y
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 ...
   y ,: ' 1' {~ x nos y
abcabcabcabcabcabcab--abcabcabcabcabcabcab--abcabcabcabcabcabcab--abcabcabcabcab
1        1            1        1            1        1            1             

   t ,: ' 1' {~ 'aaa' nos t=. 80$'a'
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1    

   t ,: ' 1' {~ x nos t=. 80$x=. 'no overlap '
no overlap no overlap no overlap no overlap no overlap no overlap no overlap no 
1          1          1          1          1          1          1             

Finally, in my previous msg, regarding when there could be an overlapping 
substring, instead of saying that "if a prefix of x occurs more than once 
as a substring in x", I should have said that:  An overlapping substring 
can occur if a prefix of x occurs as a suffix of x (other than the trivial 
case of the entire of x).