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
