On Tue, Jun 4, 2013 at 11:52 AM, Mike Müller <[email protected]> wrote:
> 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.
I don't know any really good solutions, but let me paste here the
simple solutions I've shown in irc.
First, I generated a random test input.
]t=: 'ABCDE'{~ 5|+/\1+?70$4
EADAEBDACBEDECDACAEDBDBCABDABEDBEAEDCEBABCABCECADADADBACDCECECEABDADBC
Second, I've made a solution where I tried comparing each shift of the
string with itself and find long enough sequences of equality in that.
If after shifting the string by n you get n consecutive equalities,
you've found a square of 2*n letters length.
l #~ l <: t ([: >./ [: (*>:)/\. =)"1 (l=.>:i.<.-:#t)|.!.''"0 _ t
2 3
NB. ^ shows there are repeated substrings of length 2 and 3
NB. I hope
Then I've shown a simpler solution where I simply generate all the
substrings and the same length substrings following them and string
compare them.
NB. of course, you could just try a solution by taknig substrings
l #~ (l=.>:i.<.-:#t) (4 :'1 e. x (}.=-@[}.]) x <\ y'"0 _) t
2 3
NB. ^ comparing substrings, but that would take O(n^3) time of course
--
Ambrus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
