squares=:3 : 0
n=.+:i.>.-:#y
strings=.~.,2 4 6 8<\y
a:-.~strings#~(-:/@$~2,-:@#)&>strings
)
squares 'bonbon'
+------+
|bonbon|
+------+
s=:'aababaabb'
squares s
+--+--+----+----+
|aa|bb|abab|baba|
+--+--+----+----+
squares 'square'
squares 'square-free'
+--+
|ee|
+--+
]t=: 'ABCDE'{~ 5|+/\1+?70$4
CACBDADEBEDBABABCBDCACBCBDBDECACDACBCECADCACEACEAEDBACDEDBEABCECDCBCEA
squares t
+----+----+----+----+------+------+
|BABA|ABAB|CBCB|BDBD|ACEACE|CEACEA|
+----+----+----+----+------+------+
On Tue, Jun 4, 2013 at 3:52 AM, Mike Müller <[email protected]> wrote:
> I asked about this problem in #jsoftware on Freenode, where it was
> mentioned to me that this might be of broader interest,
> so I will repeat my question here and hope to get some other interested in
> this topic.
>
> I am interested in finding squares in strings. A square is a string of the
> form uu, for some string u.
> For instance, 'bonbon' is a square. My first problem would be to check if
> a string is square-free,
> which means, that no factor (substring) of the string is a square.
> For example, 'square' is square-free, but 'square-free' is not (as the
> square 'ee' is a factor thereof)
>
> As I'm just learning J, I would be interested in "nice" ways to do this in
> J, not necessarily the fastest ones.
> This problem can be solved in linear time, see for instance [1], but I'm
> more interested in how to do it "the J way".
> As a starter, I can check if a string s is a square like that: 3 <: +/ s
> E. s,s
>
> Another problem would be to calculate the number of distinct squares in a
> string.
> I think this is also best explained by an example. Let s =. 'aababaabb'.
> Then the distinct squares appearing in s are 'aa, 'bb', 'abab', and 'baba'.
> So the number of distinct squares is 4. Note that the word _distinct_ is
> important here, as 'aa' occurs twice,
> but we only count it once.
>
> There's also some theoretical motivation for this second problem, as it is
> shown that this number is at most 2n,
> for any string of length n [2]. It is further conjectured that it is in
> fact at most n, but this is an open problem,
> and the best bound known so far is 2n - log(n) [3].
>
> I would be interested to see how these problems could be solved nicely in
> J,
> and hope to learn more of this fascinating language. Thank you!
>
> Mike
>
>
> [1] M. G. Main and R. J. Lorentz. Linear time recognition of squarefree
> strings. In Combinatorial
> Algorithms on Words, volume F12 of NATO ASI Series, pages 271–278.
> Springer, 1985.
>
> [2]Fraenkel, A. S., & Simpson, J. (1998). How many squares can a string
> contain?.
> Journal of Combinatorial Theory, Series A, 82(1), 112-120.
>
> [3]Ilie, L. (2007). A note on the number of squares in a word.
> Theoretical Computer Science, 380(3), 373-376.
>
>
>
>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
