Rep-string
You are encouraged to solve this task according to the task description, using any language you may know.
Given a series of ones and zeroes in a string, define a repeated string or rep-string as a string which is created by repeating a substring of the first N characters of the string truncated on the right to the length of the input string, and in which the substring appears repeated at least twice in the original.
For example, the string '10011001100' is a rep-string as the leftmost four characters of '1001' are repeated three times and truncated on the right to give the original string.
Note that the requirement for having the repeat occur two or more times means that the repeating unit is never longer than half the length of the input string.
The task is to:
- Write a function/subroutine/method/... that takes a string and returns an indication of if it is a rep-string and the repeated string. (Either the string that is repeated, or the number of repeated characters would suffice).
- There may be multiple sub-strings that make a string a rep-string - in that case an indication of all, or the longest, or the shortest would suffice.
- Use the function to indicate the repeating substring if any, in the following:
'1001110011' '1110111011' '0010010010' '1010101010' '1111111111' '0100101101' '0100100' '101' '11' '00' '1'
- Show your output on this page.
Ada
<lang Ada>with Ada.Command_Line, Ada.Text_IO, Ada.Strings.Fixed;
procedure Rep_String is
function Find_Largest_Rep_String(S:String) return String is
L: Natural := S'Length;
begin
for I in reverse 1 .. L/2 loop
declare use Ada.Strings.Fixed; T: String := S(S'First .. S'First + I-1); -- the first I characters of S U: String := (1+(L/I)) * T; -- repeat T so often that U'Length >= L begin -- compare first L characers of U with S if U(U'First .. U'First + S'Length -1) = S then return T; -- T is a rep-string end if; end;
end loop;
return ""; -- no rep string;
end Find_Largest_Rep_String;
X: String := Ada.Command_Line.Argument(1);
Y: String := Find_Largest_Rep_String(X);
begin
if Y="" then
Ada.Text_IO.Put_Line("No rep-string for """ & X & """");
else
Ada.Text_IO.Put_Line("Longest rep-string for """& X &""": """& Y &"""");
end if;
end Rep_String;</lang>
- Output:
> ./rep_string 1001110011 Longest rep-string for "1001110011": "10011" > ./rep_string 1110111011 Longest rep-string for "1110111011": "1110" > ./rep_string 0010010010 Longest rep-string for "0010010010": "001" > ./rep_string 1010101010 Longest rep-string for "1010101010": "1010" > ./rep_string 1111111111 Longest rep-string for "1111111111": "11111" > ./rep_string 0100101101 No rep-string for "0100101101" > ./rep_string 0100100 Longest rep-string for "0100100": "010" > ./rep_string 101 No rep-string for "101" > ./rep_string 11 Longest rep-string for "11": "1" > ./rep_string 00 Longest rep-string for "00": "0" > ./rep_string 1 No rep-string for "1"
AutoHotkey
<lang AutoHotkey>In := ["1001110011", "1110111011", "0010010010", "1010101010"
, "1111111111", "0100101101", "0100100", "101", "11", "00", "1"]
for k, v in In Out .= RepString(v) "`t" v "`n" MsgBox, % Out
RepString(s) { Loop, % StrLen(s) // 2 { i := A_Index Loop, Parse, s { pos := Mod(A_Index, i) if (A_LoopField != SubStr(s, !pos ? i : pos, 1)) continue, 2 } return SubStr(s, 1, i) } return "N/A" }</lang>
- Output:
10011 1001110011 1110 1110111011 001 0010010010 10 1010101010 1 1111111111 N/A 0100101101 010 0100100 N/A 101 1 11 0 00 N/A 1
Bracmat
<lang bracmat>( ( rep-string
= reps L x y
. ( reps
= x y z
. !arg:(?x.?y)
& ( @(!y:!x ?z)&reps$(!x.!z)
| @(!x:!y ?)
)
)
& ( :?L
& @( !arg
: %?x
!x
( ?y
& reps$(!x.!y)
& !x !L:?L
& ~
)
)
| !L:
& out$(str$(!arg " is not a rep-string"))
| out$(!arg ":" !L)
)
)
& rep-string$1001110011 & rep-string$1110111011 & rep-string$0010010010 & rep-string$1010101010 & rep-string$1111111111 & rep-string$0100101101 & rep-string$0100100 & rep-string$101 & rep-string$11 & rep-string$00 & rep-string$1 );</lang> Output:
1001110011 : 10011 1110111011 : 1110 0010010010 : 001 1010101010 : 1010 10 1111111111 : 11111 1111 111 11 1 0100101101 is not a rep-string 0100100 : 010 101 is not a rep-string 11 : 1 00 : 0 1 is not a rep-string
C++
<lang cpp>#include <string>
- include <vector>
- include <boost/regex.hpp>
bool is_repstring( const std::string & teststring , std::string & repunit ) {
std::string regex( "^(.+)\\1+(.*)$" ) ;
boost::regex e ( regex ) ;
boost::smatch what ;
if ( boost::regex_match( teststring , what , e , boost::match_extra ) ) {
std::string firstbracket( what[1 ] ) ;
std::string secondbracket( what[ 2 ] ) ;
if ( firstbracket.length( ) >= secondbracket.length( ) &&
firstbracket.find( secondbracket ) != std::string::npos ) { repunit = firstbracket ;
} } return !repunit.empty( ) ;
}
int main( ) {
std::vector<std::string> teststrings { "1001110011" , "1110111011" , "0010010010" ,
"1010101010" , "1111111111" , "0100101101" , "0100100" , "101" , "11" , "00" , "1" } ;
std::string theRep ;
for ( std::string myString : teststrings ) {
if ( is_repstring( myString , theRep ) ) {
std::cout << myString << " is a rep string! Here is a repeating string:\n" ; std::cout << theRep << " " ;
}
else {
std::cout << myString << " is no rep string!" ;
}
theRep.clear( ) ;
std::cout << std::endl ;
}
return 0 ;
}</lang>
- Output:
1001110011 is a rep string! Here is a repeating string: 10011 1110111011 is a rep string! Here is a repeating string: 1110 0010010010 is a rep string! Here is a repeating string: 001 1010101010 is a rep string! Here is a repeating string: 1010 1111111111 is a rep string! Here is a repeating string: 11111 0100101101 is no rep string! 0100100 is a rep string! Here is a repeating string: 010 101 is no rep string! 11 is a rep string! Here is a repeating string: 1 00 is a rep string! Here is a repeating string: 0 1 is no rep string!
D
Two different algorithms. The second is from the Perl 6 entry. <lang d>import std.stdio, std.string, std.conv, std.range, std.algorithm;
size_t repString1(in string s) pure /*nothrow*/ {
foreach_reverse (immutable n; 1 .. s.length / 2 + 1)
if (s.take(n).cycle.take(s.length).equal(s))
return n;
return 0;
}
size_t repString2(in string s) pure /*nothrow*/ {
immutable bits = s.to!ulong(2);
foreach_reverse (immutable left; 1 .. s.length / 2 + 1) {
immutable right = s.length - left;
if ((bits ^ (bits >> left)) == ((bits >> right) << right))
return left;
}
return 0;
}
void main() {
immutable words = "1001110011 1110111011 0010010010 1010101010
1111111111 0100101101 0100100 101 11 00 1";
foreach (immutable w; words.split) {
immutable r1 = w.repString1;
assert(r1 == w.repString2);
if (r1)
w.chunks(r1).join(" ").writeln;
else
writeln(w, " (no repeat)");
}
}</lang>
- Output:
10011 10011 1110 1110 11 001 001 001 0 1010 1010 10 11111 11111 0100101101 (no repeat) 010 010 0 101 (no repeat) 1 1 0 0 1 (no repeat)
Go
<lang go>package main
import (
"fmt" "strings"
)
func rep(s string) int {
for x := len(s) / 2; x > 0; x-- {
if strings.HasPrefix(s, s[x:]) {
return x
}
}
return 0
}
const m = ` 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1`
func main() {
for _, s := range strings.Fields(m) {
if n := rep(s); n > 0 {
fmt.Printf("%q %d rep-string %q\n", s, n, s[:n])
} else {
fmt.Printf("%q not a rep-string\n", s)
}
}
}</lang>
- Output:
"1001110011" 5 rep-string "10011" "1110111011" 4 rep-string "1110" "0010010010" 3 rep-string "001" "1010101010" 4 rep-string "1010" "1111111111" 5 rep-string "11111" "0100101101" not a rep-string "0100100" 3 rep-string "010" "101" not a rep-string "11" 1 rep-string "1" "00" 1 rep-string "0" "1" not a rep-string
Icon and Unicon
The following works in both languages.
<lang unicon>procedure main(A)
every write(s := !A,": ",(repString(s) | "Not a rep string!")\1)
end
procedure repString(s)
rs := s[1+:*s/2] while (*rs > 0) & (s ~== lrepl(rs,*s,rs)) do rs := rs[1:-1] return (*rs > 0, rs)
end
procedure lrepl(s1,n,s2) # The standard left() procedure won't work.
while *s1 < n do s1 ||:= s2 return s1[1+:n]
end</lang>
Sample output:
->rs 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 1 1110111011: 1110 0010010010: 001 1010101010: 1010 1111111111: 11111 0100101101: Not a rep string! 0100100: 010 101: Not a rep string! 11: 1 1: Not a rep string! ->
J
Here's a test:
<lang j>isRepStr=: +./@((] -: $@] $ $)"0 1~1+[:i.<.@-:@#)</lang>
Example use:
<lang j> isRepStr'1001110011' 1
isRepStr'1110111011'
1
isRepStr'0010010010'
1
isRepStr'1010101010'
1
isRepStr'1111111111'
1
isRepStr'0100101101'
0
isRepStr'0100100'
1
isRepStr'101'
0
isRepStr'11'
1
isRepStr'00'
1
isRepStr'1'
0</lang>
We could also report the lengths of the repeated prefix, though this seems more arbitrary:
<lang j>nRepStr=: 0 -.~ (([ * ] -: $@] $ $)"0 1~1+[:i.<.@-:@#)</lang>
With the above examples:
<lang j> nRepStr'1001110011' 5
nRepStr'1110111011'
4
nRepStr'0010010010'
3
nRepStr'1010101010'
2 4
nRepStr'1111111111'
1 2 3 4 5
nRepStr'0100101101'
nRepStr'0100100'
3
nRepStr'101'
nRepStr'11'
1
nRepStr'00'
1
nRepStr'1'
</lang>
Here, the "non-str-rep" cases are indicated by an empty list of prefix lengths.
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
/* REXX ***************************************************************
- 11.05.2013 Walter Pachl
- /
runSample(arg) return
/**
* Test for rep-strings * @param s_str a string to check for rep-strings * @return Rexx string: boolean indication of reps, length, repeated value */
method repstring(s_str) public static
s_str_n = s_str.length()
rep_str =
Loop lx = s_str.length() % 2 to 1 By -1
If s_str.substr(lx + 1, lx) = s_str.left(lx) Then Leave lx
End lx
If lx > 0 Then Do label reps
rep_str = s_str.left(lx)
Loop ix = 1 By 1
If s_str.substr(ix * lx + 1, lx) <> rep_str Then
Leave ix
End ix
If rep_str.copies(s_str_n).left(s_str.length()) <> s_str Then
rep_str =
End reps
Return (rep_str.length() > 0) rep_str.length() rep_str
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) public static
parse arg samples
if samples = then -
samples = -
'1001110011' -
'1110111011' -
'0010010010' -
'1010101010' -
'1111111111' -
'0100101101' -
'0100100' -
'101' -
'11' -
'00' -
'1'
loop w_ = 1 to samples.words() in_str = samples.word(w_) parse repstring(in_str) is_rep_str rep_str_len rep_str
sq = 'in_str'
tstrlen = sq.length().max(20)
sq=sq.right(tstrlen)
if is_rep_str then
Say sq 'has a repetition length of' rep_str_len "i.e. '"rep_str"'"
else
Say sq 'is not a repeated string'
end w_
return
</lang>
- Output:
'1001110011' has a repetition length of 5 i.e. '10011'
'1110111011' has a repetition length of 4 i.e. '1110'
'0010010010' has a repetition length of 3 i.e. '001'
'1010101010' has a repetition length of 4 i.e. '1010'
'1111111111' has a repetition length of 5 i.e. '11111'
'0100101101' is not a repeated string
'0100100' has a repetition length of 3 i.e. '010'
'101' is not a repeated string
'11' has a repetition length of 1 i.e. '1'
'00' has a repetition length of 1 i.e. '0'
'1' is not a repeated string
PARI/GP
<lang parigp>rep(v)=for(i=1,#v\2,for(j=i+1,#v,if(v[j]!=v[j-i],next(2)));return(i));0; v=["1001110011","1110111011","0010010010","1010101010","1111111111","0100101101","0100100","101","11","00","1"]; for(i=1,#v,print(v[i]" "rep(Vec(v[i]))))</lang>
- Output:
1001110011 5 1110111011 4 0010010010 3 1010101010 2 1111111111 1 0100101101 0 0100100 3 101 0 11 1 00 1 1 0
Perl
<lang perl>foreach (qw(1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1)) {
print "$_\n";
if (/^(.+)\1+(.*$)(?(?{ substr($1, 0, length $2) eq $2 })|(?!))/) {
print ' ' x length $1, "$1\n\n";
} else {
print " (no repeat)\n\n";
}
}</lang>
- Output:
1001110011
10011
1110111011
1110
0010010010
001
1010101010
1010
1111111111
11111
0100101101
(no repeat)
0100100
010
101
(no repeat)
11
1
00
0
1
(no repeat)
Perl 6
<lang perl6>for <1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1> {
if /^ (.+) $0+: (.*$) <?{ $0.substr(0,$1.chars) eq $1 }> / {
my $rep = $0.chars; say .substr(0,$rep), .substr($rep,$rep).trans('01' => 'ππ'), .substr($rep*2);
}
else {
say "$_ (no repeat)";
}
}</lang>
- Output:
10011πππππ 1110ππππ11 001πππ0010 1010ππππ10 11111πππππ 0100101101 (no repeat) 010πππ0 101 (no repeat) 1π 0π 1 (no repeat)
Here's a technique that relies on the fact that XORing the shifted binary number should set all the lower bits to 0 if there are repeats. (The cool thing is that shift will automatically throw away the bits on the right that you want thrown away.) This produces the same output as above. <lang perl6>sub repstr(Str $s) {
my $bits = :2($s);
for reverse 1 .. $s.chars div 2 -> $left {
my $right = $s.chars - $left; return $left if $bits +^ ($bits +> $left) == $bits +> $right +< $right;
}
}
for '1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1'.words {
if repstr $_ -> $rep {
say .substr(0,$rep), .substr($rep,$rep).trans('01' => 'ππ'), .substr($rep*2);
}
else {
say "$_ (no repeat)";
}
}</lang>
PL/I
<lang PL/I>rep: procedure options (main); /* 5 May 2015 */
declare s bit (10) varying; declare (i, k) fixed binary;
main_loop:
do s = '1001110011'b, '1110111011'b, '0010010010'b, '1010101010'b,
'1111111111'b, '0100101101'b, '0100100'b, '101'b, '11'b, '00'b, '1'b;
k = length(s);
do i = k/2 to 1 by -1;
if substr(s, 1, i) = substr(s, i+1, i) then
do;
put skip edit (s, ' is a rep-string containing ', substr(s, 1, i) ) (a);
iterate main_loop;
end;
end;
put skip edit (s, ' is not a rep-string') (a);
end;
end rep;</lang> Output:
1001110011 is a rep-string containing 10011 1110111011 is a rep-string containing 1110 0010010010 is a rep-string containing 001 1010101010 is a rep-string containing 1010 1111111111 is a rep-string containing 11111 0100101101 is a rep-string containing 010 0100100 is a rep-string containing 010 101 is not a rep-string 11 is a rep-string containing 1 00 is a rep-string containing 0 1 is not a rep-string
Python
Python: Procedural
<lang python>def is_repeated(text):
'check if the first part of the string is repeated throughout the string'
for x in range(len(text)//2, 0, -1):
if text.startswith(text[x:]): return x
return 0
matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1 """ for line in matchstr.split():
ln = is_repeated(line)
print('%r has a repetition length of %i i.e. %s'
% (line, ln, repr(line[:ln]) if ln else '*not* a rep-string'))</lang>
- Output:
'1001110011' has a repetition length of 5 i.e. '10011' '1110111011' has a repetition length of 4 i.e. '1110' '0010010010' has a repetition length of 3 i.e. '001' '1010101010' has a repetition length of 4 i.e. '1010' '1111111111' has a repetition length of 5 i.e. '11111' '0100101101' has a repetition length of 0 i.e. *not* a rep-string '0100100' has a repetition length of 3 i.e. '010' '101' has a repetition length of 0 i.e. *not* a rep-string '11' has a repetition length of 1 i.e. '1' '00' has a repetition length of 1 i.e. '0' '1' has a repetition length of 0 i.e. *not* a rep-string
Python: Functional
This returns all the possible repeated substrings <lang python>>>> def reps(text):
return [text[:x] for x in range(1, 1 + len(text) // 2)
if text.startswith(text[x:])]
>>> matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1 """ >>> print('\n'.join('%r has reps %r' % (line, reps(line)) for line in matchstr.split())) '1001110011' has reps ['10011'] '1110111011' has reps ['1110'] '0010010010' has reps ['001'] '1010101010' has reps ['10', '1010'] '1111111111' has reps ['1', '11', '111', '1111', '11111'] '0100101101' has reps [] '0100100' has reps ['010'] '101' has reps [] '11' has reps ['1'] '00' has reps ['0'] '1' has reps [] >>> </lang>
Python: Regexp
This version, inspired by the Perl 6 entry uses the regexp substitute where what the match is substituted with is returned by a function. <lang python>import re
matchstr = """\ 1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1"""
def _checker(matchobj):
g0, (g1, g2, g3, g4) = matchobj.group(0), matchobj.groups()
if not g4 and g1 and g1.startswith(g3):
return '%r repeats %r' % (g0, g1)
return '%r is not a rep-string' % (g0,)
def checkit(txt):
print(re.sub(r'(.+)(\1+)(.*)|(.*)', _checker, txt))
checkit(matchstr)</lang>
- Output:
'1001110011' repeats '10011' '1110111011' repeats '1110' '0010010010' repeats '001' '1010101010' repeats '1010' '1111111111' repeats '11111' '0100101101' is not a rep-string '0100100' repeats '010' '101' is not a rep-string '11' repeats '1' '00' repeats '0' '1' is not a rep-string
Racket
<lang Racket>#lang racket
(define (rep-string str)
(define len (string-length str))
(for/or ([n (in-range 1 len)])
(and (let loop ([from n])
(or (>= from len)
(let ([m (min (- len from) n)])
(and (equal? (substring str from (+ from m))
(substring str 0 m))
(loop (+ n from))))))
(<= n (quotient len 2))
(substring str 0 n))))
(for ([str '("1001110011"
"1110111011"
"0010010010"
"1010101010"
"1111111111"
"0100101101"
"0100100"
"101"
"11"
"00"
"1")])
(printf "~a => ~a\n" str (or (rep-string str) "not a rep-string")))</lang>
Output:
1001110011 => 10011 1110111011 => 1110 0010010010 => 001 1010101010 => 10 1111111111 => 1 0100101101 => not a rep-string 0100100 => 010 101 => not a rep-string 11 => 1 00 => 0 1 => not a rep-string
REXX
version 1
<lang rexx>/* REXX ***************************************************************
- 11.05.2013 Walter Pachl
- 14.05.2013 Walter Pachl extend to show additional rep-strings
- /
Call repstring '1001110011' Call repstring '1110111011' Call repstring '0010010010' Call repstring '1010101010' Call repstring '1111111111' Call repstring '0100101101' Call repstring '0100100' Call repstring '101' Call repstring '11' Call repstring '00' Call repstring '1' Exit
repstring: Parse Arg s sq='s' n=length(s) Do l=length(s)%2 to 1 By -1
If substr(s,l+1,l)=left(s,l) Then Leave End
If l>0 Then Do
rep_str=left(s,l)
Do i=1 By 1
If substr(s,i*l+1,l)<>rep_str Then
Leave
End
If left(copies(rep_str,n),length(s))=s Then Do
Call show_rep rep_str /* show result */
Do i=length(rep_str)-1 To 1 By -1 /* look for shorter rep_str-s */
rep_str=left(s,i)
If left(copies(rep_str,n),length(s))=s Then
Call show_rep rep_str
End
End
Else
Call show_norep
End
Else
Call show_norep
Return
show_rep:
Parse Arg rs Say right(sq,12) 'has a repetition length of' length(rs) 'i.e.' 'rs' Return
show_norep:
Say right(sq,12) 'is not a repeated string' Return</lang>
Output:
'1001110011' has a repetition length of 5 i.e. '10011'
'1110111011' has a repetition length of 4 i.e. '1110'
'0010010010' has a repetition length of 3 i.e. '001'
'1010101010' has a repetition length of 4 i.e. '1010'
'1010101010' has a repetition length of 2 i.e. '10'
'1111111111' has a repetition length of 5 i.e. '11111'
'1111111111' has a repetition length of 4 i.e. '1111'
'1111111111' has a repetition length of 3 i.e. '111'
'1111111111' has a repetition length of 2 i.e. '11'
'1111111111' has a repetition length of 1 i.e. '1'
'0100101101' is not a repeated string
'0100100' has a repetition length of 3 i.e. '010'
'101' is not a repeated string
'11' has a repetition length of 1 i.e. '1'
'00' has a repetition length of 1 i.e. '0'
'1' is not a repeated string
version 2
No checking is done to validate if the strings are binary strings (an easy-peasy-lemon-squeezy check)).
This version can handle any characters in the string except blanks (which could be used if a stemmed array would be used).
<lang rexx>/*REXX pgm determines if a string is a repString, returns min len repStr*/
s=1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1
do k=1 for words(s); _=word(s,k) /*process all the binary strings.*/
say right(_,20) rep_string(_) /*show the original & the result.*/
end /*k*/
exit /*stick a fork in it, we're done.*/ /*βββββββββββββββββββββββββββββββββββREP_STRING subroutineββββββββββββββ*/ rep_string: procedure; parse arg x; L=length(x); r_=' rep string='
do j=1 for L-1; p=left(x,j); if j>L%2 then iterate if left(copies(p,L*L),L)==x then return r_ left(p,15) '(length' j")" end /*j*/
return ' (no repetitions)' /*(sigh)βββ a failure to find rep*/</lang> output
1001110011 rep string= 10011 (length 5)
1110111011 rep string= 1110 (length 4)
0010010010 rep string= 001 (length 3)
1010101010 rep string= 10 (length 2)
1111111111 rep string= 1 (length 1)
0100101101 (no repetitions)
0100100 rep string= 010 (length 3)
101 (no repetitions)
11 rep string= 1 (length 1)
00 rep string= 0 (length 1)
1 (no repetitions)
Ruby
<lang ruby>ar = %w(1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1)
ar.each do |str|
rep_pos = (str.size/2).downto(1).find{|pos| str.start_with? str[pos..-1]}
puts str, rep_pos ? " "*rep_pos + str[0, rep_pos] : "(no repetition)", ""
end</lang>
- Output (as Perl):
1001110011
10011
1110111011
1110
0010010010
001
1010101010
1010
1111111111
11111
0100101101
(no repetition)
0100100
010
101
(no repetition)
11
1
00
0
1
(no repetition)
Run BASIC
<lang runbasic>a$ = "1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1 " a = 1 while word$(a$,a," ") <> ""
a1$ = word$(a$,a," ")
n = len(a1$)
n2 = max(1,int((n + .5) / 2))
noRep = 0
for i = 1 to n2
a2$ = a1$
r$ = left$(a1$,i)
rep = 0
for j = 1 to n
if r$ = left$(a2$,i) then
a2$ = mid$(a2$,i+1)
rep = rep + 1
end if
next j
if rep > 1 then
print a;chr$(9);a1$;chr$(9);r$;chr$(9);" Length: ";len(r$);" Repeated ";rep;" Times"
noRep = 1
end if
next i
if noRep = 0 then print a;chr$(9);a1$;" No Repeat"
a = a + 1
wend</lang>
1 1001110011 10011 Length: 5 Repeated 2 Times 2 1110111011 1 Length: 1 Repeated 3 Times 2 1110111011 1110 Length: 4 Repeated 2 Times 3 0010010010 0 Length: 1 Repeated 2 Times 3 0010010010 001 Length: 3 Repeated 3 Times 4 1010101010 10 Length: 2 Repeated 5 Times 4 1010101010 1010 Length: 4 Repeated 2 Times 5 1111111111 1 Length: 1 Repeated 10 Times 5 1111111111 11 Length: 2 Repeated 5 Times 5 1111111111 111 Length: 3 Repeated 3 Times 5 1111111111 1111 Length: 4 Repeated 2 Times 5 1111111111 11111 Length: 5 Repeated 2 Times 6 0100101101 010 Length: 3 Repeated 2 Times 7 0100100 010 Length: 3 Repeated 2 Times 8 101 No Repeat 9 11 1 Length: 1 Repeated 2 Times 10 00 0 Length: 1 Repeated 2 Times 11 1 No Repeat
Tcl
<lang tcl>proc repstring {text} {
set len [string length $text]
for {set i [expr {$len/2}]} {$i > 0} {incr i -1} {
set sub [string range $text 0 [expr {$i-1}]] set eq [string repeat $sub [expr {int(ceil($len/double($i)))}]] if {[string equal -length $len $text $eq]} { return $sub }
} error "no repetition"
}</lang> Demonstrating: <lang tcl>foreach sample {
"1001110011" "1110111011" "0010010010" "1010101010" "1111111111" "0100101101" "0100100" "101" "11" "00" "1"
} {
if {[catch {
set rep [repstring $sample] puts [format "\"%s\" has repetition (length: %d) of \"%s\"" \ $sample [string length $rep] $rep]
}]} {
puts [format "\"%s\" is not a repeated string" $sample]
}
}</lang>
- Output:
"1001110011" has repetition (length: 5) of "10011" "1110111011" has repetition (length: 4) of "1110" "0010010010" has repetition (length: 3) of "001" "1010101010" has repetition (length: 4) of "1010" "1111111111" has repetition (length: 5) of "11111" "0100101101" is not a repeated string "0100100" has repetition (length: 3) of "010" "101" is not a repeated string "11" has repetition (length: 1) of "1" "00" has repetition (length: 1) of "0" "1" is not a repeated string
zkl
<lang zkl>fcn repString(s){
foreach n in ([s.len()/2+1..1,-1]){
s[0,n]:Utils.Helpers.cycle(_).aggregate(String).walk(s.len()) :
if (_ == s and n*2<=s.len()) return(n);
}
return(False)
}</lang>
<lang zkl>fcn repString(s){
foreach n in ([s.len()/2..0,-1]){
if (s.matches(s[n,*]+"*") and n*2<=s.len()) return(n); }
return(False)
}</lang> <lang zkl>words := ("1001110011 1110111011 0010010010 1010101010 "
"1111111111 0100101101 0100100 101 11 00 1").split(" ");
foreach w in (words){
if (not n:=repString(w)) "No repeat in ".println(w);
else [0..*,n].tweak('wrap(z){ if(s:=w[z,n]) s else Void.Stop })
.walk().concat(" ").println();
}</lang>
- Output:
10011 10011 1110 1110 11 001 001 001 0 1010 1010 10 11111 11111 No repeat in 0100101101 010 010 0 No repeat in 101 1 1 0 0 No repeat in 1