I made a rather efficient way of determining in a string all u which are the
first part of a square uu .
They are given by their offset and length. sqist, which stands for SQuare In
String, does the work:
sqist 'aababaabb'
0 1
5 1
7 1
1 2
2 2
Notice that all squares, not only the distinct ones, are given. This has some
advantages:
,6#,:1 2
1 2 1 2 1 2 1 2 1 2 1 2
sqist ,6#,:1 2
0 2
1 2
2 2
3 2
4 2
5 2
6 2
7 2
8 2
0 4
1 4
2 4
3 4
4 4
0 6
This tells you that the first 2 digits are not only the beginning of a squar
u^2 , but also of u^4 and even u^6 !
sqist
'CACBDADEBEDBABABCBDCACBCBDBDECACDACBCECADCACEACEAEDBACDEDBEABCECDCBCEA'
11 2
12 2
21 2
24 2
42 3
43 3
This is difficult to check in the string itself, but (with appropriate font)
easier with
(],~ ' '-.~"1 [:":@|: 10 #.^:(_1) i.@#)
'CACBDADEBEDBABABCBDCACBCBDBDECACDACBCECADCACEACEAEDBACDEDBEABCECDCBCEA'
0000000000111111111122222222223333333333444444444455555555556666666666
0123456789012345678901234567890123456789012345678901234567890123456789
CACBDADEBEDBABABCBDCACBCBDBDECACDACBCECADCACEACEAEDBACDEDBEABCECDCBCEA
Determining the distinct squares is done by
(/: #@{.S:0)({:"1 <@:(t ~.@:{~ (+i.@+:)/"1)/.]) sqist
t=:'CACBDADEBEDBABABCBDCACBCBDBDECACDACBCECADCACEACEAEDBACDEDBEABCECDCBCEA'
+----+------+
|BABA|ACEACE|
|ABAB|CEACEA|
|CBCB| |
|BDBD| |
+----+------+
Efficiency measurement:
t=: 'ACTG'{~ 4|+/\1+10000 ?@$ 4
ts'((/: #@{.S:0)({:"1 <@:(t ~.@:{~ (+i.@+:)/"1)/.]) sqist t)'
0.37413665 1.3597274e8
The longest squares (length 16) are
>{: ((/: #@{.S:0)({:"1 <@:(t ~.@:{~ (+i.@+:)/"1)/.]) sqist t)
ACTAGGAGACTAGGAG
CTAGGAGACTAGGAGA
TAGGAGACTAGGAGAC
AGGAGACTAGGAGACT
and the number of distinct squares
+/#S:0 ((/: #@{.S:0)({:"1 <@:(t ~.@:{~ (+i.@+:)/"1)/.]) sqist t)
129
BTW, the definition of sqist:
sqist=: 3 : 0
if. 2=(3!:0)y do. q=. a.{~1+>./a.i.y else. q=: 1+>./y end.
(/:{:"1);((-i.)@# ([ <@([,.~ (-~I.)) *./\)"0 1 ]) y ="1 ny[\ (}:y),~ q #~ <.-:
ny=. #y
)
R.E. Boss
(Add your info to http://www.jsoftware.com/jwiki/Community/Demographics )
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
