[Jprogramming] split a string with a delimiter word

[Roger Hui]

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).



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

Note that "split" as defined below is not a general solution.
In x split y, if a prefix of x occurs more than once as a
substring in x, then there could be a problem:

   'abab' split '+-*abababxyzabababab123ababax789'
+---++---+++---+-----+
|+-*||xyz|||123|ax789|
+---++---+++---+-----+

To solve this kind of problem, replace E. in split by an
appropriate substring search function.  It can be based
on E. with additional code for transitive closure.



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

   split=: #@[ }.&.> ([E.,) <;.1 ,

   'abra' split 'helloabraworldabra!about'
+-----+-----+------+
|hello|world|!about|
+-----+-----+------+

NB. chop solves a different problem

   require 'misc'
   'abra' chop 'helloabraworldabra!about'
+-----+--+--+-+---+
|hello|wo|ld|!|out|
+-----+--+--+-+---+



----- Original Message ----- 
From: "June Kim" <juneaftn at gmail.com>
To: "Programming forum" <programming at jsoftware.com>
Sent: Saturday, January 07, 2006 7:13 PM
Subject: [Jprogramming] split a string with a delimiter word

Hello,

What is a standard way of splitting a string with a delimiter word in J?

For example,

   'split' split 'hellosplitworldsplit!'
+-----+-----+-+
|hello|world|!|
+-----+-----+-+

I once have tried to write the verb myself but it was way too complex
for doing such a simple thing.


----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm