Rep-string
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 two or more times, truncated on the right to the length of the input string.
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.
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).
- 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.
NetRexx
<lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols nobinary
/* REXX ***************************************************************
- 11.05.2013 Walter Pachl
- /
runSample(arg) return
method repstring(Arg) public static
Parse Arg s
maxlen = ('s').length.max(20)
sq=('s').right(maxlen)
n=s.length()
Loop l=s.length()%2 to 1 By -1
If s.substr(l+1,l)=s.left(l) Then Leave
End
If l>0 Then Do
rep_str=s.left(l)
Loop i=1 By 1
If s.substr(i*l+1,l)<>rep_str Then
Leave
End
If rep_str.copies(n).left(s.length())=s Then
Say sq 'has a repetition length of' rep_str.length() 'i.e. rep_str'
Else
Say sq 'is not a repeated string'
End
Else
Say sq 'is not a repeated string'
Return
method runSample(arg) public static
parse arg samples
if samples = then -
samples = -
'1001110011' -
'1110111011' -
'0010010010' -
'1010101010' -
'1111111111' -
'0100101101' -
'0100100' -
'101' -
'1'
loop w_ = 1 to samples.words() repstring(samples.word(w_)) end 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
'1' is not a repeated string
Perl
<lang perl>foreach (qw(1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 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)
1
(no repeat)
Perl 6
<lang perl6>for <1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 1> {
.say;
if /^ (.+) $0+ (.*$) <?{ $0.substr(0,$1.chars) eq $1 }> / {
say ' ' x $0.chars, "$0\n";
}
else {
say " (no repeat)\n";
}
}</lang>
- Output:
1001110011
10011
1110111011
1110
0010010010
001
1010101010
1010
1111111111
11111
0100101101
(no repeat)
0100100
010
101
(no repeat)
1
(no repeat)
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 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 '1' is not a rep-string
REXX
<lang rexx>/* REXX ***************************************************************
- 11.05.2013 Walter Pachl
- /
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 '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
Say sq 'has a repetition length of' length(rep_str),
'i.e.' 'rep_str'
Else
Say sq 'is not a repeated string'
End
Else
Say sq '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' '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 '1' is not a repeated string
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" "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 "1" is not a repeated string