Rep-string
(Redirected from Repeated 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.
- Task
- 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.
Other tasks related to string operations:
- Metrics
- Counting
- Word frequency
- Letter frequency
- Jewels and stones
- I before E except after C
- Bioinformatics/base count
- Count occurrences of a substring
- Count how many vowels and consonants occur in a string
- Remove/replace
- XXXX redacted
- Conjugate a Latin verb
- Remove vowels from a string
- String interpolation (included)
- Strip block comments
- Strip comments from a string
- Strip a set of characters from a string
- Strip whitespace from a string -- top and tail
- Strip control codes and extended characters from a string
- Anagrams/Derangements/shuffling
- Word wheel
- ABC problem
- Sattolo cycle
- Knuth shuffle
- Ordered words
- Superpermutation minimisation
- Textonyms (using a phone text pad)
- Anagrams
- Anagrams/Deranged anagrams
- Permutations/Derangements
- Find/Search/Determine
- ABC words
- Odd words
- Word ladder
- Semordnilap
- Word search
- Wordiff (game)
- String matching
- Tea cup rim text
- Alternade words
- Changeable words
- State name puzzle
- String comparison
- Unique characters
- Unique characters in each string
- Extract file extension
- Levenshtein distance
- Palindrome detection
- Common list elements
- Longest common suffix
- Longest common prefix
- Compare a list of strings
- Longest common substring
- Find common directory path
- Words from neighbour ones
- Change e letters to i in words
- Non-continuous subsequences
- Longest common subsequence
- Longest palindromic substrings
- Longest increasing subsequence
- Words containing "the" substring
- Sum of the digits of n is substring of n
- Determine if a string is numeric
- Determine if a string is collapsible
- Determine if a string is squeezable
- Determine if a string has all unique characters
- Determine if a string has all the same characters
- Longest substrings without repeating characters
- Find words which contains all the vowels
- Find words which contain the most consonants
- Find words which contains more than 3 vowels
- Find words whose first and last three letters are equal
- Find words with alternating vowels and consonants
- Formatting
- Substring
- Rep-string
- Word wrap
- String case
- Align columns
- Literals/String
- Repeat a string
- Brace expansion
- Brace expansion using ranges
- Reverse a string
- Phrase reversals
- Comma quibbling
- Special characters
- String concatenation
- Substring/Top and tail
- Commatizing numbers
- Reverse words in a string
- Suffixation of decimal numbers
- Long literals, with continuations
- Numerical and alphabetical suffixes
- Abbreviations, easy
- Abbreviations, simple
- Abbreviations, automatic
- Song lyrics/poems/Mad Libs/phrases
- Mad Libs
- Magic 8-ball
- 99 bottles of beer
- The Name Game (a song)
- The Old lady swallowed a fly
- The Twelve Days of Christmas
- Tokenize
- Text between
- Tokenize a string
- Word break problem
- Tokenize a string with escaping
- Split a character string based on change of character
- Sequences
11l
F reps(text)
R (1 .< 1 + text.len I/ 2).filter(x -> @text.starts_with(@text[x..])).map(x -> @text[0 .< x])
V matchstr =
|β1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1β
L(line) matchstr.split("\n")
print(β'#.' has reps #.β.format(line, reps(line)))- Output:
'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 []
ABC
HOW TO RETURN repstrings str:
PUT {} IN reps
FOR len IN {0..floor(#str/2-1)}:
PUT str|floor(#str/2-len) IN rep
PUT rep IN rpt
WHILE #rpt < #str: PUT rpt^rep IN rpt
IF rpt|#str = str: INSERT rep IN reps
RETURN reps
PUT {} IN tests
PUT "1001110011" IN tests[1]
PUT "1110111011" IN tests[2]
PUT "0010010010" IN tests[3]
PUT "1010101010" IN tests[4]
PUT "1111111111" IN tests[5]
PUT "0100101101" IN tests[6]
PUT "0100100" IN tests[7]
PUT "101" IN tests[8]
PUT "11" IN tests[9]
PUT "00" IN tests[10]
PUT "1" IN tests[11]
FOR t IN tests:
WRITE t, repstrings t /- Output:
1001110011: {"10011"}
1110111011: {"1110"}
0010010010: {"001"}
1010101010: {"10"; "1010"}
1111111111: {"1"; "11"; "111"; "1111"; "11111"}
0100101101: {}
0100100: {"010"}
101: {}
11: {"1"}
00: {"0"}
1: {}
Action!
BYTE FUNC IsCycle(CHAR ARRAY s,sub)
BYTE i,j,count
IF sub(0)=0 OR s(0)<sub(0) THEN
RETURN (0)
FI
j=1 count=0
FOR i=1 TO s(0)
DO
IF s(i)#sub(j) THEN
RETURN (0)
FI
j==+1
IF j>sub(0) THEN
j=1 count==+1
FI
OD
IF count>1 THEN
RETURN (1)
FI
RETURN (0)
PROC Test(CHAR ARRAY s)
CHAR ARRAY sub
BYTE len,count
PrintF("%S -> ",s)
count=0
FOR len=1 TO s(0)-1
DO
SCopyS(sub,s,1,len)
IF IsCycle(s,sub) THEN
IF count>0 THEN
Print(", ")
FI
Print(sub)
count==+1
FI
OD
IF count=0 THEN
Print("none")
FI
PutE()
RETURN
PROC Main()
Test("1001110011")
Test("1110111011")
Test("0010010010")
Test("1010101010")
Test("1111111111")
Test("0100101101")
Test("0100100")
Test("101")
Test("11")
Test("00")
Test("1")
RETURN- Output:
Screenshot from Atari 8-bit computer
1001110011 -> 10011 1110111011 -> 1110 0010010010 -> 001 1010101010 -> 10, 1010 1111111111 -> 1, 11, 111, 1111, 11111 0100101101 -> none 0100100 -> 010 101 -> none 11 -> 1 00 -> 0 1 -> none
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;
- 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"
ALGOL 68
# procedure to find the longest rep-string in a given string #
# the input string is not validated to contain only "0" and "1" characters #
PROC longest rep string = ( STRING input )STRING:
BEGIN
STRING result := "";
# ensure the string we are working on has a lower-bound of 1 #
STRING str = input[ AT 1 ];
# work backwards from half the input string looking for a rep-string #
FOR string length FROM UPB str OVER 2 BY -1 TO 1
WHILE
STRING left substring = str[ 1 : string length ];
# if the left substgring repeated a sufficient number of times #
# (truncated on the right) is equal to the original string, then #
# we have found the longest rep-string #
STRING repeated string = ( left substring
* ( ( UPB str OVER string length ) + 1 )
)[ 1 : UPB str ];
IF str = repeated string
THEN
# found a rep-string #
result := left substring;
FALSE
ELSE
# not a rep-string, keep looking #
TRUE
FI
DO
SKIP
OD;
result
END; # longest rep string #
# test the longest rep string procedure #
BEGIN
[]STRING tests = ( "1001110011"
, "1110111011"
, "0010010010"
, "1010101010"
, "1111111111"
, "0100101101"
, "0100100"
, "101"
, "11"
, "00"
, "1"
);
FOR test number FROM LWB tests TO UPB tests
DO
STRING rep string = longest rep string( tests[ test number ] );
print( ( tests[ test number ]
, ": "
, IF rep string = ""
THEN "no rep string"
ELSE "longest rep string: """ + rep string + """"
FI
, newline
)
)
OD
END- Output:
1001110011: longest rep string: "10011" 1110111011: longest rep string: "1110" 0010010010: longest rep string: "001" 1010101010: longest rep string: "1010" 1111111111: longest rep string: "11111" 0100101101: no rep string 0100100: longest rep string: "010" 101: no rep string 11: longest rep string: "1" 00: longest rep string: "0" 1: no rep string
APL
This function returns a list of all possible repeated substrings. It returns the empty list if there are none.
rep β β’ (β’(/β¨)(ββ£)β‘Β¨(β’β£)β΄Β¨β’) β³β(β0.5Γβ’)βΒ¨β
- Output:
rep '1001110011'
10011
rep '1110111011'
1110
rep '0010010010'
001
rep '1010101010'
10 1010
rep '1111111111'
1 11 111 1111 11111
rep '0100101101'
rep '0100100'
010
rep '101'
rep '11'
1
rep '00'
0
rep ,'1'
AppleScript
------------------------REP-CYCLES-------------------------
-- repCycles :: String -> [String]
on repCycles(xs)
set n to length of xs
script isCycle
on |Ξ»|(cs)
xs = takeCycle(n, cs)
end |Ξ»|
end script
filter(isCycle, tail(inits(take(quot(n, 2), xs))))
end repCycles
-- cycleReport :: String -> [String]
on cycleReport(xs)
set reps to repCycles(xs)
if isNull(reps) then
{xs, "(n/a)"}
else
{xs, item -1 of reps}
end if
end cycleReport
---------------------------TEST----------------------------
on run
set samples to {"1001110011", "1110111011", "0010010010", Β¬
"1010101010", "1111111111", "0100101101", "0100100", Β¬
"101", "11", "00", "1"}
unlines(cons("Longest cycle:" & linefeed, Β¬
map(intercalate(" -> "), Β¬
map(cycleReport, samples))))
end run
---------------------GENERIC FUNCTIONS---------------------
-- concat :: [[a]] -> [a] | [String] -> String
on concat(xs)
if length of xs > 0 and class of (item 1 of xs) is string then
set acc to ""
else
set acc to {}
end if
repeat with i from 1 to length of xs
set acc to acc & item i of xs
end repeat
acc
end concat
-- cons :: a -> [a] -> [a]
on cons(x, xs)
{x} & xs
end cons
-- filter :: (a -> Bool) -> [a] -> [a]
on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |Ξ»|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |Ξ»|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- inits :: [a] -> [[a]]
-- inits :: String -> [String]
on inits(xs)
script elemInit
on |Ξ»|(_, i, xs)
items 1 thru i of xs
end |Ξ»|
end script
script charInit
on |Ξ»|(_, i, xs)
text 1 thru i of xs
end |Ξ»|
end script
if class of xs is string then
{""} & map(charInit, xs)
else
{{}} & map(elemInit, xs)
end if
end inits
-- intercalate :: Text -> [Text] -> Text
on intercalate(strText)
script
on |Ξ»|(xs)
set {dlm, my text item delimiters} to {my text item delimiters, strText}
set strJoined to xs as text
set my text item delimiters to dlm
return strJoined
end |Ξ»|
end script
end intercalate
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |Ξ»|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |Ξ»| : f
end script
end if
end mReturn
-- isNull :: [a] -> Bool
on isNull(xs)
xs = {}
end isNull
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- quot :: Integral a => a -> a -> a
on quot(n, m)
n div m
end quot
-- replicate :: Int -> a -> [a]
on replicate(n, a)
set out to {}
if n < 1 then return out
set dbl to {a}
repeat while (n > 1)
if (n mod 2) > 0 then set out to out & dbl
set n to (n div 2)
set dbl to (dbl & dbl)
end repeat
return out & dbl
end replicate
-- tail :: [a] -> [a]
on tail(xs)
if length of xs > 1 then
items 2 thru -1 of xs
else
{}
end if
end tail
-- take :: Int -> [a] -> [a]
on take(n, xs)
if class of xs is string then
if n > 0 then
text 1 thru min(n, length of xs) of xs
else
""
end if
else
if n > 0 then
items 1 thru min(n, length of xs) of xs
else
{}
end if
end if
end take
-- takeCycle :: Int -> [a] -> [a]
on takeCycle(n, xs)
set lng to length of xs
if lng β₯ n then
set cycle to xs
else
set cycle to concat(replicate((n div lng) + 1, xs))
end if
if class of xs is string then
items 1 thru n of cycle as string
else
items 1 thru n of cycle
end if
end takeCycle
-- unlines :: [String] -> String
on unlines(xs)
|Ξ»|(xs) of intercalate(linefeed)
end unlines
- Output:
Longest cycle: 1001110011 -> 10011 1110111011 -> 1110 0010010010 -> 001 1010101010 -> 1010 1111111111 -> 11111 0100101101 -> (n/a) 0100100 -> 010 101 -> (n/a) 11 -> 1 00 -> 0 1 -> (n/a)
Arturo
repeated?: function [text][
loop ((size text)/2)..0 'x [
if prefix? text slice text x (size text)-1 [
(x>0)? -> return slice text 0 x-1
-> return false
]
]
return false
]
strings: {
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1
}
loop split.lines strings 'str [
rep: repeated? str
if? false = rep ->
print [str "-> *not* a rep-string"]
else ->
print [str "->" rep "( length:" size rep ")"]
]
- Output:
1001110011 -> 10011 ( length: 5 ) 1110111011 -> 1110 ( length: 4 ) 0010010010 -> 001 ( length: 3 ) 1010101010 -> 1010 ( length: 4 ) 1111111111 -> 11111 ( length: 5 ) 0100101101 -> *not* a rep-string 0100100 -> 010 ( length: 3 ) 101 -> *not* a rep-string 11 -> 1 ( length: 1 ) 00 -> 0 ( length: 1 ) 1 -> *not* a rep-string
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"
}
- 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
BaCon
all$ = "1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1"
FOR word$ IN all$
FOR x = LEN(word$)/2 DOWNTO 1
ex$ = EXPLODE$(word$, x)
FOR st$ IN UNIQ$(ex$)
IF NOT(REGEX(HEAD$(ex$, 1), "^" & st$)) THEN CONTINUE 2
NEXT
PRINT "Repeating string: ", word$, " -> ", HEAD$(ex$, 1)
CONTINUE 2
NEXT
PRINT "Not a repeating string: ", word$
NEXT
- Output:
Repeating string: 1001110011 -> 10011 Repeating string: 1110111011 -> 1110 Repeating string: 0010010010 -> 001 Repeating string: 1010101010 -> 1010 Repeating string: 1111111111 -> 11111 Not a repeating string: 0100101101 Repeating string: 0100100 -> 010 Not a repeating string: 101 Repeating string: 11 -> 1 Repeating string: 00 -> 0 Not a repeating string: 1
BASIC
10 DEFINT I: DEFSTR S,T
20 READ S: IF S="" THEN END
30 IF LEN(S)<2 THEN 80 ELSE FOR I = LEN(S)\2 TO 1 STEP -1
40 T = ""
50 IF LEN(T)<LEN(S) THEN T=T+LEFT$(S,I): GOTO 50
60 IF LEFT$(T,LEN(S))=S THEN PRINT S;": ";LEFT$(S,I): GOTO 20
70 NEXT I
80 PRINT S;": none"
90 GOTO 20
100 DATA "1001110011","1110111011"
110 DATA "0010010010","1010101010"
120 DATA "1111111111","0100101101"
130 DATA "0100100","101"
140 DATA "11","00"
150 DATA "1",""
- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 1010 1111111111: 11111 0100101101: none 0100100: 010 101: none 11: 1 00: 0 1: none
Applesoft BASIC
10 FOR Q = 0 TO 0: READ S$:L = LEN (S$): ON L > 0 GOSUB 20: NEXT Q: END
20 LET R$ = ""
30 ON L > 1 GOSUB 70
40 PRINT S$":"R$ MID$ (" NONE",1,5 * ( LEN (R$) = 0))
50 LET Q = - 1
60 RETURN
70 FOR I = INT (L / 2) TO 1 STEP - 1
80 T$ = "": FOR T = 0 TO 0:T$ = T$ + LEFT$ (S$,I):T = - ( LEN (T$) < L): NEXT T: IF LEFT$ (T$,L) = S$ THEN R$ = R$ + " " + LEFT$ (S$,I)
90 NEXT I: RETURN
100 DATA "1001110011","1110111011"
110 DATA "0010010010","1010101010"
120 DATA "1111111111","0100101101"
130 DATA "0100100","101"
140 DATA "11","00"
150 DATA "1",""
- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 1010 10 1111111111: 11111 1111 111 11 1 0100101101: NONE 0100100: 010 101: NONE 11: 1 00: 0 1: NONE
BCPL
get "libhdr"
// Returns the length of the longest rep-string
// (0 if there are none)
let repstring(s) = valof
$( for i = s%0/2 to 1 by -1 do
$( for j = 1 to i
$( let k = i
while j+k <= s%0 do
$( unless s%(j+k)=s%j goto next
k := k + i
$)
$)
resultis i
next: loop
$)
resultis 0
$)
// Print first N characters of string
let writefirst(s, n) be
$( let x = s%0
s%0 := n
writes(s)
s%0 := x
$)
// Test string
let rep(s) be
$( let n = repstring(s)
writef("%S: ",s)
test n=0
do writes("none")
or writefirst(s,n)
wrch('*N')
$)
let start() be
$( rep("1001110011")
rep("1110111011")
rep("0010010010")
rep("1010101010")
rep("1111111111")
rep("0100101101")
rep("0100100")
rep("101")
rep("11")
rep("00")
rep("1")
$)- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 1010 1111111111: 11111 0100101101: none 0100100: 010 101: none 11: 1 00: 0 1: none
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
);- 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
BQN
# Returns a list of all rep-strings
Repsβ(ββ Γ·2Λ)((β£β₯β Β¨ββ’)/β’)(<β‘Β¨β β₯Β¨1ββ)/1ββ
# Tests
testsββ¨
"1001110011", "1110111011", "0010010010",
"1010101010", "1111111111", "0100101101",
"0100100", "101", "11", "00", "1"
β©
βΎΒ΄{ π©βΎ':'βΎ(β’Fmt Reps π©)βΎ@+10 }Β¨tests
- Output:
"1001110011:β¨ ""10011"" β© 1110111011:β¨ ""1110"" β© 0010010010:β¨ ""001"" β© 1010101010:β¨ ""10"" ""1010"" β© 1111111111:β¨ ""1"" ""11"" ""111"" ""1111"" ""11111"" β© 0100101101:β¨β© 0100100:β¨ ""010"" β© 101:β¨β© 11:β¨ ""1"" β© 00:β¨ ""0"" β© 1:β¨β© "
C
Longest substring
#include <stdio.h>
#include <string.h>
int repstr(char *str)
{
if (!str) return 0;
size_t sl = strlen(str) / 2;
while (sl > 0) {
if (strstr(str, str + sl) == str)
return sl;
--sl;
}
return 0;
}
int main(void)
{
char *strs[] = { "1001110011", "1110111011", "0010010010", "1111111111",
"0100101101", "0100100", "101", "11", "00", "1" };
size_t strslen = sizeof(strs) / sizeof(strs[0]);
size_t i;
for (i = 0; i < strslen; ++i) {
int n = repstr(strs[i]);
if (n)
printf("\"%s\" = rep-string \"%.*s\"\n", strs[i], n, strs[i]);
else
printf("\"%s\" = not a rep-string\n", strs[i]);
}
return 0;
}
- Output:
"1001110011" = rep-string "10011" "1110111011" = rep-string "1110" "0010010010" = rep-string "001" "1111111111" = rep-string "11111" "0100101101" = not a rep-string "0100100" = rep-string "010" "101" = not a rep-string "11" = rep-string "1" "00" = rep-string "0" "1" = not a rep-string
shortest substring
// strstr : Returns a pointer to the first occurrence of str2 in str1, or a null pointer if str2 is not part of str1.
// size_t is an unsigned integer typ
// lokks for the shortest substring
int repstr(char *str)
{
if (!str) return 0; // if empty input
size_t sl = 1;
size_t sl_max = strlen(str) ;
while (sl < sl_max) {
if (strstr(str, str + sl) == str) // How it works ???? It checks the whole string str
return sl;
++sl;
}
return 0;
}
C#
using System;
public class RepString
{
static readonly string[] input = {"1001110011", "1110111011", "0010010010",
"1010101010", "1111111111", "0100101101", "0100100", "101", "11",
"00", "1", "0100101"};
public static void Main(string[] args)
{
foreach (string s in input)
Console.WriteLine($"{s} : {repString(s)}");
}
static string repString(string s)
{
int len = s.Length;
for (int part = len / 2; part > 0; part--)
{
int tail = len % part;
if (tail > 0 && !s.Substring(0, tail).Equals(s.Substring(len - tail)))
continue;
bool isRepeated = true;
for (int j = 0; j < len / part - 1; j++)
{
int a = j * part;
int b = (j + 1) * part;
int c = (j + 2) * part;
if (!s.Substring(a, part).Equals(s.Substring(b, part)))
{
isRepeated = false;
break;
}
}
if (isRepeated)
return s.Substring(0, part);
}
return "none";
}
}
- Output:
1001110011 : 10011 1110111011 : 1110 0010010010 : 001 1010101010 : 1010 1111111111 : 11111 0100101101 : none 0100100 : 010 101 : none 11 : 1 00 : 0 1 : none 0100101 : none
C++
#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 ;
}
- 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!
Without external libraries
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>
std::string repeat(const std::string& text, const int32_t& repetitions) {
std::stringstream stream;
std::fill_n(std::ostream_iterator<std::string>(stream), repetitions, text);
return stream.str();
}
std::vector<std::string> rep_string(const std::string& text) {
std::vector<std::string> repetitions;
for ( uint64_t len = 1; len <= text.length() / 2; ++len ) {
std::string possible = text.substr(0, len);
uint64_t quotient = text.length() / len;
uint64_t remainder = text.length() % len;
std::string candidate = repeat(possible, quotient) + possible.substr(0, remainder);
if ( candidate == text ) {
repetitions.emplace_back(possible);
}
}
return repetitions;
}
int main() {
const std::vector<std::string> tests = { "1001110011", "1110111011", "0010010010",
"1010101010", "1111111111", "0100101101", "0100100", "101", "11", "00", "1" };
std::cout << "The longest rep-strings are:" << std::endl;
for ( const std::string& test : tests ) {
std::vector<std::string> repeats = rep_string(test);
std::string result = repeats.empty() ? "Not a rep-string" : repeats.back();
std::cout << std::setw(10) << test << " -> " << result << std::endl;
}
}
- Output:
The longest rep-strings are:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> Not a rep-string
0100100 -> 010
101 -> Not a rep-string
11 -> 1
00 -> 0
1 -> Not a rep-string
Clojure
(defn rep-string [s]
(let [len (count s)
first-half (subs s 0 (/ len 2))
test-group (take-while seq (iterate butlast first-half))
test-reptd (map #(take len (cycle %)) test-group)]
(some #(= (seq s) %) test-reptd)))
- Output:
(def test-strings ["1001110011"
"1110111011"
"0010010010"
"1010101010"
"1111111111"
"0100101101"
"0100100"
"101"
"11"
"00"
"1"])
(map (juxt identity rep-string) test-strings)
(["1001110011" true] ["1110111011" true] ["0010010010" true] ["1010101010" true] ["1111111111" true] ["0100101101" nil] ["0100100" true] ["101" nil] ["11" true] ["00" true] ["1" nil])
CLU
rep_strings = iter (s: string) yields (string)
for len: int in int$from_to_by(string$size(s)/2, 1, -1) do
repstr: string := string$substr(s, 1, len)
attempt: string := ""
while string$size(attempt) < string$size(s) do
attempt := attempt || repstr
end
if s = string$substr(attempt, 1, string$size(s)) then
yield(repstr)
end
end
end rep_strings
start_up = proc ()
as = array[string]
po: stream := stream$primary_output()
tests: as := as$["1001110011","1110111011","0010010010","1010101010",
"1111111111","0100101101","0100100","101","11","00",
"1"]
for test: string in as$elements(tests) do
stream$puts(po, test || ": ")
for rep_str: string in rep_strings(test) do
stream$puts(po, "<" || rep_str || "> ")
end
stream$putc(po, '\n')
end
end start_up- Output:
1001110011: <10011> 1110111011: <1110> 0010010010: <001> 1010101010: <1010> <10> 1111111111: <11111> <1111> <111> <11> <1> 0100101101: 0100100: <010> 101: 11: <1> 00: <0> 1:
Common Lisp
(ql:quickload :alexandria)
(defun rep-stringv (a-str &optional (max-rotation (floor (/ (length a-str) 2))))
;; Exit condition if no repetition found.
(cond ((< max-rotation 1) "Not a repeating string")
;; Two checks:
;; 1. Truncated string must be equal to rotation by repetion size.
;; 2. Remaining chars (rest-str) are identical to starting chars (beg-str)
((let* ((trunc (* max-rotation (truncate (length a-str) max-rotation)))
(truncated-str (subseq a-str 0 trunc))
(rest-str (subseq a-str trunc))
(beg-str (subseq a-str 0 (rem (length a-str) max-rotation))))
(and (string= beg-str rest-str)
(string= (alexandria:rotate (copy-seq truncated-str) max-rotation)
truncated-str)))
;; If both checks pass, return the repeting string.
(subseq a-str 0 max-rotation))
;; Recurse function reducing length of rotation.
(t (rep-stringv a-str (1- max-rotation)))))
- Output:
(setf test-strings '("1001110011"
"1110111011"
"0010010010"
"1010101010"
"1111111111"
"0100101101"
"0100100"
"101"
"11"
"00"
"1"
))
(loop for item in test-strings
collecting (cons item (rep-stringv item)))
(("1001110011" . "10011") ("1110111011" . "1110") ("0010010010" . "001")
("1010101010" . "1010") ("1111111111" . "11111")
("0100101101" . "Not a repeating string") ("0100100" . "010")
("101" . "Not a repeating string") ("11" . "1") ("00" . "0")
("1" . "Not a repeating string"))
Crystal
def rep(s : String) : Int32
x = s.size // 2
while x > 0
return x if s.starts_with? s[x..]
x -= 1
end
0
end
def main
%w(
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1
).each do |s|
n = rep s
puts n > 0 ? "\"#{s}\" #{n} rep-string \"#{s[..(n - 1)]}\"" : "\"#{s}\" not a rep-string"
end
end
main
- 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
D
Two different algorithms. The second is from the Raku entry.
import std.stdio, std.string, std.conv, std.range, std.algorithm,
std.ascii, std.typecons;
Nullable!(size_t, 0) repString1(in string s) pure nothrow @safe @nogc
in {
//assert(s.all!isASCII);
assert(s.representation.all!isASCII);
} body {
immutable sr = s.representation;
foreach_reverse (immutable n; 1 .. sr.length / 2 + 1)
if (sr.take(n).cycle.take(sr.length).equal(sr))
return typeof(return)(n);
return typeof(return)();
}
Nullable!(size_t, 0) repString2(in string s) pure @safe /*@nogc*/
in {
assert(s.countchars("01") == s.length);
} body {
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 typeof(return)(left);
}
return typeof(return)();
}
void main() {
immutable words = "1001110011 1110111011 0010010010 1010101010
1111111111 0100101101 0100100 101 11 00 1".split;
foreach (immutable w; words) {
immutable r1 = w.repString1;
//assert(r1 == w.repString2);
immutable r2 = w.repString2;
assert((r1.isNull && r2.isNull) || r1 == r2);
if (r1.isNull)
writeln(w, " (no repeat)");
else
writefln("%(%s %)", w.chunks(r1));
}
}
- 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)
Delphi
program Rep_string;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
const
m = '1001110011'#10 +
'1110111011'#10 +
'0010010010'#10 +
'1010101010'#10 +
'1111111111'#10 +
'0100101101'#10 +
'0100100'#10 +
'101'#10 +
'11'#10 +
'00'#10 +
'1';
function Rep(s: string; var sub:string): Integer;
var
x: Integer;
begin
for x := s.Length div 2 downto 1 do
begin
sub := s.Substring(x);
if s.StartsWith(sub) then
exit(x);
end;
sub := '';
Result := 0;
end;
begin
for var s in m.Split([#10]) do
begin
var sub := '';
var n := rep(s,sub);
if n > 0 then
writeln(format('"%s" %d rep-string "%s"', [s, n, sub]))
else
writeln(format('"%s" not a rep-string', [s]));
end;
{$IFNDEF UNIX}readln;{$ENDIF}
end.
DuckDB
create or replace function repString(s) as (
if (length(s) < 2, null,
(with recursive size_t as (select length(s) as size),
cte as
(select ((size % 2) + (size // 2)) as len, '' as t, false as found
from size_t
union all
select len-1 as len,
s[1:len] as t,
s == (repeat(s[1:len], (size // len))
|| coalesce(t[1:(size % len)], ''))
as found
from cte, size_t
where len > 0 and found = false
)
select first(t)
from cte
where found
))
);
select s, repString(s)
from unnest(
[
'1001110011',
'1110111011',
'0010010010',
'1010101010',
'1111111111',
'0100101101',
'0100100',
'101',
'11',
'00',
'1'
]) _(s);
- Output:
ββββββββββββββ¬βββββββββββββββ β s β repstring(s) β β varchar β varchar β ββββββββββββββΌβββββββββββββββ€ β 1001110011 β 10011 β β 1110111011 β 1110 β β 0010010010 β 001 β β 1010101010 β 1010 β β 1111111111 β 11111 β β 0100101101 β β β 0100100 β 010 β β 101 β β β 11 β 1 β β 00 β 0 β β 1 β β ββββββββββββββ΄βββββββββββββββ€ β 11 rows 2 columns β βββββββββββββββββββββββββββββ
Dyalect
func rep(s) {
var x = s.Length() / 2
while x > 0 {
if s.StartsWith(s.Substring(x)) {
return x
}
x -= 1
}
return 0
}
let m = [
"1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
]
for s in m {
if (rep(s) is n) && n > 0 {
print("\(s) \(n) rep-string \(s.Substring(n))")
} else {
print("\(s) not a rep-string")
}
}- Output:
1001110011 5 rep-string 10011 1110111011 4 rep-string 111011 0010010010 3 rep-string 0010010 1010101010 4 rep-string 101010 1111111111 5 rep-string 11111 0100101101 not a rep-string 0100100 3 rep-string 0100 101 not a rep-string 11 1 rep-string 1 00 1 rep-string 0 1 not a rep-string
EasyLang
func$ repstr s$ .
sl = len s$ div 2 + 1
while sl > 1
r$ = substr s$ sl 999
if r$ = substr s$ 1 len r$
return substr r$ 1 (sl - 1)
.
sl -= 1
.
return ""
.
repeat
s$ = input
until s$ = ""
print s$ & " -> " & repstr s$
.
input_data
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1
EchoLisp
(lib 'list) ;; list-rotate
;; a list is a rep-list if equal? to itself after a rotation of lam units
;; lam <= list length / 2
;; truncate to a multiple of lam before rotating
;; try cycles in decreasing lam order (longest wins)
(define (cyclic? cyclic)
(define len (length cyclic))
(define trunc null)
(if (> len 1)
(for ((lam (in-range (quotient len 2) 0 -1)))
(set! trunc (take cyclic (- len (modulo len lam))))
#:break (equal? trunc (list-rotate trunc lam)) => (list->string (take cyclic lam))
'no-rep )
'too-short-no-rep))
- Output:
(define strings '["1001110011" "1110111011" "0010010010" "1010101010"
"1111111111" "0100101101" "0100100" "101" "11" "00" "1"])
(define (task strings)
(for-each (lambda (s)
(writeln s (cyclic? (string->list s)))) strings))
(task strings)
"1001110011" "10011"
"1110111011" "1110"
"0010010010" "001"
"1010101010" "1010"
"1111111111" "11111"
"0100101101" no-rep
"0100100" "010"
"101" no-rep
"11" "1"
"00" "0"
"1" too-short-no-rep
Ed
This is not a comprehensive solution, as it only handles sequences repeated twice. But it's good enough for a tool not intended for general-purpose programming.
H
g/([01]*)\1(.*)/s//\1/
,p
Q- Output:
10011 1110 001 1010 11111 010 010 1 0
Elixir
defmodule Rep_string do
def find(""), do: IO.puts "String was empty (no repetition)"
def find(str) do
IO.puts str
rep_pos = Enum.find(div(String.length(str),2)..1, fn pos ->
String.starts_with?(str, String.slice(str, pos..-1))
end)
if rep_pos && rep_pos>0 do
IO.puts String.duplicate(" ", rep_pos) <> String.slice(str, 0, rep_pos)
else
IO.puts "(no repetition)"
end
IO.puts ""
end
end
strs = ~w(1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1)
Enum.each(strs, fn str -> Rep_string.find(str) end)
- Output:
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)
Excel
LAMBDA
Binding the following lambda expressions to the names REPCYCLES and TAKECYCLESTRING in the Excel Workbook Name Manager:
(See LAMBDA: The ultimate Excel worksheet function)
REPCYCLES
=LAMBDA(s,
LET(
n, LEN(s),
xs, FILTERP(
LAMBDA(pfx,
s = TAKECYCLESTRING(n)(pfx)
)
)(
TAILCOLS(
INITS(
MID(s, 1, QUOTIENT(n, 2))
)
)
),
IF(ISERROR(xs), NA(), xs)
)
)
TAKECYCLESTRING
=LAMBDA(n,
LAMBDA(s,
LET(
lng, LEN(s),
MID(
IF(n < lng,
s,
REPT(s, CEILING.MATH(n / lng))
),
1, n
)
)
)
)
And also assuming the following generic bindings in the Name Manager:
FILTERP
=LAMBDA(p,
LAMBDA(xs,
FILTER(xs, p(xs))
)
)
INITS
=LAMBDA(s,
MID(
s,
1, SEQUENCE(
1, 1 + LEN(s),
0, 1
)
)
)
LASTCOL
=LAMBDA(xs,
IF(AND(1 = COLUMNS(xs), ISBLANK(xs)),
NA(),
INDEX(xs, 1, COLUMNS(xs))
)
)
TAILCOLS
=LAMBDA(xs,
IF(1 < COLUMNS(xs),
INDEX(
xs,
1,
SEQUENCE(1, COLUMNS(xs) - 1, 2, 1)
),
NA()
)
)
- Output:
| fx | =LASTCOL(REPCYCLES(A2)) | ||
|---|---|---|---|
| A | B | ||
| 1 | String | Longest cycle, if any | |
| 2 | 1001110011 | 10011 | |
| 3 | 1110111011 | 1110 | |
| 4 | 0010010010 | 001 | |
| 5 | 1010101010 | 1010 | |
| 6 | 1111111111 | 11111 | |
| 7 | 0100101101 | #N/A | |
| 8 | 0100100 | 010 | |
| 9 | 101 | #N/A | |
| 10 | 11 | 1 | |
| 11 | 00 | 0 | |
| 12 | 1 | #N/A | |
F#
let isPrefix p (s : string) = s.StartsWith(p)
let getPrefix n (s : string) = s.Substring(0,n)
let repPrefixOf str =
let rec isRepeatedPrefix p s =
if isPrefix p s then isRepeatedPrefix p (s.Substring (p.Length))
else isPrefix s p
let rec getLongestRepeatedPrefix n =
if n = 0 then None
elif isRepeatedPrefix (getPrefix n str) str then Some(getPrefix n str)
else getLongestRepeatedPrefix (n-1)
getLongestRepeatedPrefix (str.Length/2)
[<EntryPoint>]
let main argv =
printfn "Testing for rep-string (and showing the longest repeated prefix in case):"
[
"1001110011"
"1110111011"
"0010010010"
"1010101010"
"1111111111"
"0100101101"
"0100100"
"101"
"11"
"00"
"1"
] |>
List.map (fun s ->
match repPrefixOf s with | None -> s + ": NO" | Some(p) -> s + ": YES ("+ p + ")")
|> List.iter (printfn "%s")
0
- Output:
Testing for rep-string (and showing the longest repeated prefix in case): 1001110011: YES (10011) 1110111011: YES (1110) 0010010010: YES (001) 1010101010: YES (1010) 1111111111: YES (11111) 0100101101: NO 0100100: YES (010) 101: NO 11: YES (1) 00: YES (0) 1: NO
Factor
USING: formatting grouping kernel math math.ranges qw sequences ;
IN: rosetta-code.rep-string
: (find-rep-string) ( str -- str )
dup dup length 2/ [1,b]
[ <groups> [ head? ] monotonic? ] with find nip dup
[ head ] [ 2drop "N/A" ] if ;
: find-rep-string ( str -- str )
dup length 1 <= [ drop "N/A" ] [ (find-rep-string) ] if ;
qw{ 1001110011 1110111011 0010010010 1010101010 1111111111
0100101101 0100100 101 11 00 1 }
"Shortest cycle:\n\n" printf
[ dup find-rep-string "%-10s -> %s\n" printf ] each
- Output:
Shortest cycle: 1001110011 -> 10011 1110111011 -> 1110 0010010010 -> 001 1010101010 -> 10 1111111111 -> 1 0100101101 -> N/A 0100100 -> 010 101 -> N/A 11 -> 1 00 -> 0 1 -> N/A
Forth
: rep-string ( caddr1 u1 -- caddr2 u2 ) \ u2=0: not a rep-string
2dup dup >r r@ 2/ /string
begin 2over 2over string-prefix? 0= over r@ < and while -1 /string repeat
r> swap - >r 2drop r> ;
: test ( caddr u -- )
2dup type ." has "
rep-string ?dup 0= if drop ." no " else type ." as " then
." repeating substring" cr ;
: tests
s" 1001110011" test
s" 1110111011" test
s" 0010010010" test
s" 1010101010" test
s" 1111111111" test
s" 0100101101" test
s" 0100100" test
s" 101" test
s" 11" test
s" 00" test
s" 1" test ;
- Output:
cr tests
1001110011 has 10011 as repeating substring
1110111011 has 1110 as repeating substring
0010010010 has 001 as repeating substring
1010101010 has 1010 as repeating substring
1111111111 has 11111 as repeating substring
0100101101 has no repeating substring
0100100 has 010 as repeating substring
101 has no repeating substring
11 has 1 as repeating substring
00 has 0 as repeating substring
1 has no repeating substring
ok
FreeBASIC
Data "1001110011", "1110111011", "0010010010", "1010101010", "1111111111", "0100101101", "0100100", "101", "11", "00", "1", ""
Function rep(c As String, n As Integer) As String
Dim As String r
For i As Integer = 1 To n
r = r + c
Next i
Return r
End Function
Do
Dim As String p, b = "", t, s
Read p : If p = "" Then Exit Do
Dim As Integer l = Len(p), m = Int(l / 2)
For i As Integer = m To 1 Step -1
t = Left(p, i)
s = rep(t, l / i + 1)
If p = Left(s, l) Then b = t : Exit For
Next i
If b = "" Then
Print p; " no es una cadena repetida"
Else
Print p; " secuencia m s larga: "; b
End If
Loop
Sleep
- Output:
1001110011 secuencia mΓ‘s larga: 10011 1110111011 secuencia mΓ‘s larga: 1110 0010010010 secuencia mΓ‘s larga: 001 1010101010 secuencia mΓ‘s larga: 1010 1111111111 secuencia mΓ‘s larga: 11111 0100101101 no es una cadena repetida 0100100 secuencia mΓ‘s larga: 010 101 no es una cadena repetida 11 secuencia mΓ‘s larga: 1 00 secuencia mΓ‘s larga: 0 1 no es una cadena repetida
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)
}
}
}
- 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
Haskell
import Data.List (inits, maximumBy)
import Data.Maybe (fromMaybe)
repstring :: String -> Maybe String
-- empty strings are not rep strings
repstring [] = Nothing
-- strings with only one character are not rep strings
repstring [_] = Nothing
repstring xs
| any (`notElem` "01") xs = Nothing
| otherwise = longest xs
where
-- length of the original string
lxs = length xs
-- half that length
lq2 = lxs `quot` 2
-- make a string of same length using repetitions of a part
-- of the original string, and also return the substring used
subrepeat x = (x, take lxs $ concat $ repeat x)
-- check if a repeated string matches the original string
sndValid (_, ys) = ys == xs
-- make all possible strings out of repetitions of parts of
-- the original string, which have max. length lq2
possible = map subrepeat . take lq2 . tail . inits
-- filter only valid possibilities, and return the substrings
-- used for building them
valid = map fst . filter sndValid . possible
-- see which string is longer
compLength a b = compare (length a) (length b)
-- get the longest substring that, repeated, builds a string
-- that matches the original string
longest ys = case valid ys of
[] -> Nothing
zs -> Just $ maximumBy compLength zs
main :: IO ()
main =
mapM_ processIO examples
where
examples =
[ "1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
]
process = fromMaybe "Not a rep string" . repstring
processIO xs = do
putStr (xs <> ": ")
putStrLn $ process xs
- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 1010 1111111111: 11111 0100101101: Not a rep string 0100100: 010 101: Not a rep string 11: 1 00: 0 1: Not a rep string
Or, alternatively:
import Data.Bool (bool)
import Data.List (inits, intercalate, transpose)
------------------------ REP-CYCLES ----------------------
repCycles :: String -> [String]
repCycles cs =
filter
((cs ==) . take n . cycle)
((tail . inits) $ take (quot n 2) cs)
where
n = length cs
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
fTable
"Longest cycles:\n"
id
((flip bool "n/a" . last) <*> null)
repCycles
[ "1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
]
------------------------- GENERIC ------------------------
fTable ::
String ->
(a -> String) ->
(b -> String) ->
(a -> b) ->
[a] ->
String
fTable s xShow fxShow f xs =
let rjust n c = drop . length <*> (replicate n c <>)
w = maximum (length . xShow <$> xs)
in unlines $
s :
fmap
( ((<>) . rjust w ' ' . xShow)
<*> ((" -> " <>) . fxShow . f)
)
xs
- Output:
Longest cycles:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> n/a
0100100 -> 010
101 -> n/a
11 -> 1
00 -> 0
1 -> n/a
Icon and Unicon
The following works in both languages.
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
- 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:
replengths=: >:@i.@<.@-:@#
rep=: $@] $ $
isRepStr=: +./@((] -: rep)"0 1~ replengths)
Example use:
isRepStr '1001110011'
1
Tests=: noun define
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1
)
isRepStr;._2 Tests NB. run all tests
1 1 1 1 1 0 1 0 1 1 0
We could also report the lengths of the repeated prefix, though this seems more arbitrary:
nRepStr=: 0 -.~ (([ * ] -: rep)"0 1~ replengths)
With the above examples:
":@nRepStr;._2 Tests
5
4
3
2 4
1 2 3 4 5
3
1
1
Here, the "non-str-rep" cases are indicated by an empty list of prefix lengths.
Java
public class RepString {
static final String[] input = {"1001110011", "1110111011", "0010010010",
"1010101010", "1111111111", "0100101101", "0100100", "101", "11",
"00", "1", "0100101"};
public static void main(String[] args) {
for (String s : input)
System.out.printf("%s : %s%n", s, repString(s));
}
static String repString(String s) {
int len = s.length();
outer:
for (int part = len / 2; part > 0; part--) {
int tail = len % part;
if (tail > 0 && !s.substring(0, tail).equals(s.substring(len - tail)))
continue;
for (int j = 0; j < len / part - 1; j++) {
int a = j * part;
int b = (j + 1) * part;
int c = (j + 2) * part;
if (!s.substring(a, b).equals(s.substring(b, c)))
continue outer;
}
return s.substring(0, part);
}
return "none";
}
}
- Output:
1001110011 : 10011 1110111011 : 1110 0010010010 : 001 1010101010 : 1010 1111111111 : 11111 0100101101 : none 0100100 : 010 101 : none 11 : 1 00 : 0 1 : none 0100101 : none
Alternative version avoiding the use of 'goto'
import java.util.ArrayList;
import java.util.List;
public final class RepStrings {
public static void main(String[] aArgs) {
List<String> tests = List.of( "1001110011", "1110111011", "0010010010",
"1010101010", "1111111111", "0100101101", "0100100", "101", "11", "00", "1" );
System.out.println("The longest rep-strings are:");
for ( String test : tests ) {
List<String> repeats = repString(test);
String result = repeats.isEmpty() ? "Not a rep-string" : repeats.get(repeats.size() - 1);
System.out.println(String.format("%10s%s%s", test, " -> ", result));
}
}
private static List<String> repString(String aText) {
List<String> repetitions = new ArrayList<String>();
for ( int length = 1; length <= aText.length() / 2; length++ ) {
String possible = aText.substring(0, length);
int quotient = aText.length() / length;
int remainder = aText.length() % length;
String candidate = possible.repeat(quotient) + possible.substring(0, remainder);
if ( candidate.equals(aText) ) {
repetitions.add(possible);
}
}
return repetitions;
}
}
- Output:
The longest rep-strings are:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> Not a rep-string
0100100 -> 010
101 -> Not a rep-string
11 -> 1
00 -> 0
1 -> Not a rep-string
JavaScript
ES6
(() => {
'use strict';
const main = () => {
// REP-CYCLES -------------------------------------
// repCycles :: String -> [String]
const repCycles = s => {
const n = s.length;
return filter(
x => s === take(n, cycle(x)).join(''),
tail(inits(take(quot(n, 2), s)))
);
};
// TEST -------------------------------------------
console.log(fTable(
'Longest cycles:\n',
str,
xs => 0 < xs.length ? concat(last(xs)) : '(none)',
repCycles,
[
'1001110011',
'1110111011',
'0010010010',
'1010101010',
'1111111111',
'0100101101',
'0100100',
'101',
'11',
'00',
'1'
]
));
};
// GENERIC FUNCTIONS ----------------------------------
// concat :: [[a]] -> [a]
// concat :: [String] -> String
const concat = xs =>
0 < xs.length ? (() => {
const unit = 'string' !== typeof xs[0] ? (
[]
) : '';
return unit.concat.apply(unit, xs);
})() : [];
// cycle :: [a] -> Generator [a]
function* cycle(xs) {
const lng = xs.length;
let i = 0;
while (true) {
yield(xs[i])
i = (1 + i) % lng;
}
}
// filter :: (a -> Bool) -> [a] -> [a]
const filter = (f, xs) => xs.filter(f);
// fTable :: String -> (a -> String) ->
// (b -> String) -> (a -> b) -> [a] -> String
const fTable = (s, xShow, fxShow, f, xs) => {
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
const
ys = xs.map(xShow),
w = Math.max(...ys.map(length));
return s + '\n' + zipWith(
(a, b) => a.padStart(w, ' ') + ' -> ' + b,
ys,
xs.map(x => fxShow(f(x)))
).join('\n');
};
// inits([1, 2, 3]) -> [[], [1], [1, 2], [1, 2, 3]
// inits('abc') -> ["", "a", "ab", "abc"]
// inits :: [a] -> [[a]]
// inits :: String -> [String]
const inits = xs => [
[]
]
.concat(('string' === typeof xs ? xs.split('') : xs)
.map((_, i, lst) => lst.slice(0, 1 + i)));
// last :: [a] -> a
const last = xs =>
0 < xs.length ? xs.slice(-1)[0] : undefined;
// Returns Infinity over objects without finite length.
// This enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc
// length :: [a] -> Int
const length = xs =>
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
// quot :: Int -> Int -> Int
const quot = (n, m) => Math.floor(n / m);
// str :: a -> String
const str = x => x.toString();
// tail :: [a] -> [a]
const tail = xs => 0 < xs.length ? xs.slice(1) : [];
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = (n, xs) =>
'GeneratorFunction' !== xs.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
// Use of `take` and `length` here allows zipping with non-finite lists
// i.e. generators like cycle, repeat, iterate.
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = (f, xs, ys) => {
const
lng = Math.min(length(xs), length(ys)),
as = take(lng, xs),
bs = take(lng, ys);
return Array.from({
length: lng
}, (_, i) => f(as[i], bs[i], i));
};
// MAIN ---
return main();
})();
- Output:
Longest cycles:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> (none)
0100100 -> 010
101 -> (none)
11 -> 1
00 -> 0
1 -> (none)
jq
For each test string, a JSON object giving details about the prefixes that satisfy the requirement is presented; if the string is not a rep-string, the empty array ([]) is shown.
def is_rep_string:
# if self is a rep-string then return [n, prefix]
# where n is the number of full occurrences of prefix
def _check(prefix; n; sofar):
length as $length
| if length <= (sofar|length) then [n, prefix]
else (sofar+prefix) as $sofar
| if startswith($sofar) then _check(prefix; n+1; $sofar)
elif ($sofar|length) > $length and
startswith($sofar[0:$length]) then [n, prefix]
else [0, prefix]
end
end
;
[range (1; length/2 + 1) as $i
| .[0:$i] as $prefix
| _check($prefix; 1; $prefix)
| select( .[0] > 1 ) ]
;Example:
def test:
(
"1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
) | { (.) : is_rep_string }
;
test- Output:
$ jq -n -c -f rep-string.jq
{"1001110011":[[2,"10011"]]}
{"1110111011":[[2,"1110"]]}
{"0010010010":[[3,"001"]]}
{"1010101010":[[5,"10"],[2,"1010"]]}
{"1111111111":[[10,"1"],[5,"11"],[3,"111"],[2,"1111"],[2,"11111"]]}
{"0100101101":[]}
{"0100100":[[2,"010"]]}
{"101":[]}
{"11":[[2,"1"]]}
{"00":[[2,"0"]]}
{"1":[]}
Julia
repstring returns a list of all of the substrings of its input that are the repeating units of a rep-string. If the input is not a valid rep-string, it returns an empty list. Julia indexes strings, including those that contain multi-byte characters, at the byte level. Because of this characteristic, repstring indexes its input using the chr2ind built-in.
function repstring(r::AbstractString)
n = length(r)
replst = String[]
for m in 1:nΓ·2
s = r[1:chr2ind(r, m)]
if (s ^ cld(n, m))[1:chr2ind(r, n)] != r continue end
push!(replst, s)
end
return replst
end
tests = ["1001110011", "1110111011", "0010010010", "1010101010", "1111111111",
"0100101101", "0100100", "101", "11", "00", "1",
"\u2200\u2203\u2200\u2203\u2200\u2203\u2200\u2203"]
for r in tests
replst = repstring(r)
if isempty(replst)
println("$r is not a rep-string.")
else
println("$r is a rep-string of ", join(replst, ", "), ".")
end
end
- Output:
1001110011 is a rep-string of 10011.
1110111011 is a rep-string of 1110.
0010010010 is a rep-string of 001.
1010101010 is a rep-string of 10, 1010.
1111111111 is a rep-string of 1, 11, 111, 1111, 11111.
0100101101 is not a rep-string.
0100100 is a rep-string of 010.
101 is not a rep-string.
11 is a rep-string of 1.
00 is a rep-string of 0.
1 is not a rep-string.
ββββββββ is a rep-string of ββ, ββββ.
Kotlin
// version 1.0.6
fun repString(s: String): MutableList<String> {
val reps = mutableListOf<String>()
if (s.length < 2) return reps
for (c in s) if (c != '0' && c != '1') throw IllegalArgumentException("Not a binary string")
for (len in 1..s.length / 2) {
val t = s.take(len)
val n = s.length / len
val r = s.length % len
val u = t.repeat(n) + t.take(r)
if (u == s) reps.add(t)
}
return reps
}
fun main(args: Array<String>) {
val strings = listOf(
"1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
)
println("The (longest) rep-strings are:\n")
for (s in strings) {
val reps = repString(s)
val size = reps.size
println("${s.padStart(10)} -> ${if (size > 0) reps[size - 1] else "Not a rep-string"}")
}
}
- Output:
The (longest) rep-strings are:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> Not a rep-string
0100100 -> 010
101 -> Not a rep-string
11 -> 1
00 -> 0
1 -> Not a rep-string
LFE
The heavy lifting:
(defun get-reps (text)
(lists:filtermap
(lambda (x)
(case (get-rep text (lists:split x text))
('() 'false)
(x `#(true ,x))))
(lists:seq 1 (div (length text) 2))))
(defun get-rep
((text `#(,head ,tail))
(case (string:str text tail)
(1 head)
(_ '()))))
Displaying the results:
(defun report
((`#(,text ()))
(io:format "~p has no repeating characters.~n" `(,text)))
((`#(,text (,head . ,_)))
(io:format "~p repeats ~p every ~p character(s).~n" `(,text ,head ,(length head))))
((data)
(lists:map
#'report/1
(lists:zip data (lists:map #'get-reps/1 data)))
'ok))
Running the code:
> (set data '("1001110011"
"1110111011"
"0010010010"
"1010101010"
"1111111111"
"0100101101"
"0100100"
"101"
"11"
"00"
"1"))
> (report data)
"1001110011" repeats "10011" every 5 character(s).
"1110111011" repeats "1110" every 4 character(s).
"0010010010" repeats "001" every 3 character(s).
"1010101010" repeats "10" every 2 character(s).
"1111111111" repeats "1" every 1 character(s).
"0100101101" has no repeating characters.
"0100100" repeats "010" every 3 character(s).
"101" has no repeating characters.
"11" repeats "1" every 1 character(s).
"00" repeats "0" every 1 character(s).
"1" has no repeating characters.
ok
Maple
The built-in Period command in the StringTools package computes the length of the longest repeated prefix.
repstr? := proc( s :: string )
local per := StringTools:-Period( s );
if 2 * per <= length( s ) then
true, s[ 1 .. per ]
else
false, ""
end if
end proc:For the given set of test strings, we can generate the following output.
> Test := ["1001110011", "1110111011", "0010010010", "1010101010", "1111111111", \
"0100101101", "0100100", "101", "11", "00", "1"]:
> for s in Test do
> printf( "%*s\t%5s %s\n", 3 + max(map(length,Test)), s, repstr?( s ) )
> end do:
1001110011 true 10011
1110111011 true 1110
0010010010 true 001
1010101010 true 10
1111111111 true 1
0100101101 false
0100100 true 010
101 false
11 true 1
00 true 0
1 falseMathematica /Wolfram Language
Mathematica is based on pattern-based matching, so this is very easily implemented:
RepStringQ[strin_String]:=StringCases[strin,StartOfString~~Repeated[x__,{2,\[Infinity]}]~~y___~~EndOfString/;StringMatchQ[x,StartOfString~~y~~___]:>x, Overlaps -> All]
Trying it out for the test-strings:
str={"1001110011","1110111011","0010010010","1010101010","1111111111","0100101101","0100100","101","11","00","1"};
{#,RepStringQ[#]}&/@str//Grid
- Output:
1001110011 {10011}
1110111011 {1110}
0010010010 {001}
1010101010 {1010,10,10}
1111111111 {11111,1111,111,11,11,1,1}
0100101101 {}
0100100 {010}
101 {}
11 {1}
00 {0}
1 {}
It outputs all the possibilities for a rep-string, if there is no rep-string it will show an empty list {}.
Miranda
main :: [sys_message]
main = [Stdout (lay (map test tests))]
test :: [char]->[char]
test s = s ++ ": " ++ show (repstrings s)
tests :: [[char]]
tests = ["1001110011", "1110111011", "0010010010", "1010101010",
"1111111111", "0100101101", "0100100", "101", "11", "00",
"1"]
repstrings :: [*]->[[*]]
repstrings s = filter matching bases
where bases = [take n s | n<-[1..#s div 2]]
matching r = s = take (#s) (concat (repeat r))- Output:
1001110011: ["10011"] 1110111011: ["1110"] 0010010010: ["001"] 1010101010: ["10","1010"] 1111111111: ["1","11","111","1111","11111"] 0100101101: [] 0100100: ["010"] 101: [] 11: ["1"] 00: ["0"] 1: []
Modula-2
MODULE RepStrings;
FROM InOut IMPORT Write, WriteString, WriteLn, WriteCard;
FROM Strings IMPORT Copy, Length;
(* Find the length of the longest rep-string given a string.
If there is no rep-string, the result is 0. *)
PROCEDURE repLength(s: ARRAY OF CHAR): CARDINAL;
VAR strlen, replen, i, j: CARDINAL;
ok: BOOLEAN;
BEGIN
strlen := Length(s);
FOR replen := strlen DIV 2 TO 1 BY -1 DO
ok := TRUE;
i := 0;
WHILE ok AND (i < replen) DO
j := i + replen;
WHILE (i+j < strlen) AND (s[i] = s[j]) DO
j := j + replen;
END;
ok := ok AND (i+j >= strlen);
INC(i);
END;
IF ok THEN RETURN replen; END;
END;
RETURN 0;
END repLength;
(* Store the longest rep-string in the given buffer. *)
PROCEDURE repString(in: ARRAY OF CHAR; VAR out: ARRAY OF CHAR);
VAR len: CARDINAL;
BEGIN
len := repLength(in);
Copy(in, 0, len, out);
out[len] := CHR(0);
END repString;
(* Display the longest rep-string given a string *)
PROCEDURE rep(s: ARRAY OF CHAR);
VAR buf: ARRAY [0..63] OF CHAR;
BEGIN
WriteString(s);
WriteString(": ");
repString(s, buf);
WriteString(buf);
WriteLn();
END rep;
(* Test cases *)
BEGIN
rep("1001110011");
rep("1110111011");
rep("0010010010");
rep("1010101010");
rep("1111111111");
rep("0100101101");
rep("0100100");
rep("101");
rep("11");
rep("00");
rep("1");
END RepStrings.
- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 1010 1111111111: 11111 0100101101: 0100100: 010 101: 11: 1 00: 0 1:
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
- 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
NGS
tests = [
'1001110011'
'1110111011'
'0010010010'
'1010101010'
'1111111111'
'0100101101'
'0100100'
'101'
'11'
'00'
'1'
]
F is_repeated(s:Str) (s.len()/2..0).first(F(x) s.starts_with(s[x..null]))
{
tests.each(F(test) {
local r = is_repeated(test)
echo("${test} ${if r "has repetition of length ${r} (i.e. ${test[0..r]})" "is not a rep-string"}")
})
}- Output:
1001110011 has repetition of length 5 (i.e. 10011)1110111011 has repetition of length 4 (i.e. 1110) 0010010010 has repetition of length 3 (i.e. 001) 1010101010 has repetition of length 4 (i.e. 1010) 1111111111 has repetition of length 5 (i.e. 11111) 0100101101 is not a rep-string 0100100 has repetition of length 3 (i.e. 010) 101 is not a rep-string 11 has repetition of length 1 (i.e. 1) 00 has repetition of length 1 (i.e. 0)
1 is not a rep-string
Nim
import strutils
proc isRepeated(text: string): int =
for x in countdown(text.len div 2, 0):
if text.startsWith(text[x..text.high]): return x
const matchstr = """1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1"""
for line in matchstr.split():
let ln = isRepeated(line)
echo "'", line, "' has a repetition length of ", ln, " i.e ",
(if ln > 0: "'" & line[0 ..< ln] & "'" else: "*not* a rep-string")
- 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
Objeck
class RepString {
function : Main(args : String[]) ~ Nil {
strings := ["1001110011", "1110111011", "0010010010", "1111111111",
"0100101101", "0100100", "101", "11", "00", "1"];
each(i : strings) {
string := strings[i];
repstring := RepString(string);
if(repstring->Size() > 0) {
"\"{$string}\" = rep-string \"{$repstring}\""->PrintLine();
}
else {
"\"{$string}\" = not a rep-string"->PrintLine();
};
};
}
function : RepString(string : String) ~ String {
offset := string->Size() / 2;
while(offset > 0) {
left := string->SubString(offset);
right := string->SubString(left->Size(),left->Size());
if(left->Equals(right)) {
if(ValidateMatch(left, string)) {
return left;
}
else {
return "";
};
};
offset--;
};
return "";
}
function : ValidateMatch(left : String, string : String) ~ Bool {
parts := string->Size() / left->Size();
tail := string->Size() % left->Size() <> 0;
for(i := 1; i < parts; i+=1;) {
offset := i * left->Size();
right := string->SubString(offset, left->Size());
if(<>left->Equals(right)) {
return false;
};
};
if(tail) {
offset := parts * left->Size();
right := string->SubString(offset, string->Size() - offset);
each(i : right) {
if(left->Get(i) <> right->Get(i)) {
return false;
};
};
};
return true;
}
}Output:
"1001110011" = rep-string "10011" "1110111011" = rep-string "1110" "0010010010" = rep-string "001" "1111111111" = rep-string "11111" "0100101101" = not a rep-string "0100100" = rep-string "010" "101" = not a rep-string "11" = rep-string "1" "00" = rep-string "0" "1" = not a rep-string
Oforth
Returns null if no rep string.
: repString(s)
| sz i |
s size dup ->sz 2 / 1 -1 step: i [
s left(sz i - ) s right(sz i -) == ifTrue: [ s left(i) return ]
]
null ;- Output:
["1001110011", "1110111011", "0010010010", "1010101010", "1111111111", "0100101101", "0100100", "101", "11", "00", "1"] map(#repString) . [10011, 1110, 001, 1010, 11111, null, 010, null, 1, 0, null] ok
PARI/GP
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]))))- Output:
1001110011 5 1110111011 4 0010010010 3 1010101010 2 1111111111 1 0100101101 0 0100100 3 101 0 11 1 00 1 1 0
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";
}
}
- 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)
Phix
Shows all possible repeated sub-strings, as Julia, but in the output style of Perl/Elixir
function list_reps(string r) sequence replist = {} integer n = length(r) for m=1 to floor(n/2) do string s = r[1..m] if join(repeat(s,floor(n/m)+1),"")[1..n]=r then replist = append(replist,s) end if end for return replist end function constant tests = {"1001110011", "1110111011", "0010010010", "1010101010", "1111111111", "0100101101", "0100100", "101", "11", "00", "1"} for i=1 to length(tests) do printf(1,"%s\n",{tests[i]}) sequence replist = list_reps(tests[i]) if length(replist)=0 then printf(1,"not a rep-string.\n") else for j=1 to length(replist) do string rj = replist[j], pad = repeat(' ',length(rj)) printf(1,"%s%s\n",{pad,rj}) end for end if printf(1,"\n") end for
- Output:
1001110011
10011
1110111011
1110
0010010010
001
1010101010
10
1010
1111111111
1
11
111
1111
11111
0100101101
not a rep-string.
0100100
010
101
not a rep-string.
11
1
00
0
1
not a rep-string.
Phixmonti
include ..\Utilitys.pmt
def repstr /# s n -- s #/
"" swap
for drop
over chain
endfor
nip
enddef
def repString /# s -- s #/
len dup var sz
2 / 1 swap 2 tolist for
var i
1 i slice var chunk
chunk sz i / 1 + repstr
1 sz slice nip over
== if chunk exitfor endif
endfor
len sz == sz 1 == or if ": No repeat string" chain else ": " swap chain chain endif
enddef
( "1001110011" "1110111011" "0010010010" "1010101010" "1111111111" "0100101101" "0100100" "101" "11" "00" "1" )
len for
get repString print nl
endfor- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 10 1111111111: 1 0100101101: No repeat string 0100100: 010 101: No repeat string 11: 1 00: 0 1: No repeat string === Press any key to exit ===
Picat
go =>
Strings = [
"1001110011", % 10011
"1110111011", % 1110
"0010010010", % 001
"1010101010", % 1010
"1111111111", % 11111
"0100101101", % no solution
"0100100", % 010
"101", % no solution
"11", % 1
"00", % 0
"1", % no solution
"", % no solution
"123123123123123", % 123123
"12312312312312", % 123123
"123123123123124", % no solution
"abcabcdabcabcdabc", % abcabcd
[1,2,3,4,1,2,3,4,1,2,3] % 1,2,3,4
],
foreach(S in Strings)
printf("%w: ", S),
if maxrep(S,Substr,N) then
println([substr=Substr,n=N])
else
println("no solution")
end
end,
nl.
% the largest repeating substring
maxrep(S,Substr,N) =>
maxof(rep(S,Substr,N),N).
rep(S,Substr,N) =>
between(1,S.length div 2, N),
Len = S.length,
Len2 = Len - (Len mod N),
Substr = slice(S,1,N),
% count the number of proper slices
SS = [1 : I in 1..N..Len2, slice(S,I,I+N-1) = Substr],
SS.length = Len div N,
% the last (truncated) slice (or []) must be a substring of Substr
Rest = slice(S,Len2+1,Len),
find(Substr,Rest,1,_).- Output:
1001110011: [substr = 10011,n = 5] 1110111011: [substr = 1110,n = 4] 0010010010: [substr = 001,n = 3] 1010101010: [substr = 1010,n = 4] 1111111111: [substr = 11111,n = 5] 0100101101: no solution 0100100: [substr = 010,n = 3] 101: no solution 11: [substr = 1,n = 1] 00: [substr = 0,n = 1] 1: no solution []: no solution 123123123123123: [substr = 123123,n = 6] 12312312312312: [substr = 123123,n = 6] 123123123123124: no solution abcabcdabcabcdabc: [substr = abcabcd,n = 7] [1,2,3,4,1,2,3,4,1,2,3]: [substr = [1,2,3,4],n = 4]
PicoLisp
(de repString (Str)
(let Lst (chop Str)
(for (N (/ (length Lst) 2) (gt0 N) (dec N))
(T
(use (Lst X)
(let H (cut N 'Lst)
(loop
(setq X (cut N 'Lst))
(NIL (head X H))
(NIL Lst T) ) ) )
N ) ) ) )Test:
(test 5 (repString "1001110011"))
(test 4 (repString "1110111011"))
(test 3 (repString "0010010010"))
(test 4 (repString "1010101010"))
(test 5 (repString "1111111111"))
(test NIL (repString "0100101101"))
(test 3 (repString "0100100"))
(test NIL (repString "101"))
(test 1 (repString "11"))
(test 1 (repString "00"))
(test NIL (repString "1"))
(test NIL (repString "0100101"))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;- 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
PL/M
100H:
DECLARE MAX$REP LITERALLY '32';
DECLARE FALSE LITERALLY '0';
DECLARE TRUE LITERALLY '1';
DECLARE CR LITERALLY '0DH';
DECLARE LF LITERALLY '0AH';
/* CP/M BDOS SYSTEM CALL */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
/* PRINTS A BYTE AS A CHARACTER */
PRINT$CHAR: PROCEDURE( CH ); DECLARE CH BYTE; CALL BDOS( 2, CH ); END;
/* PRINTS A $ TERMINATED STRING */
PRINT$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
/* PRINTS A BYTE AS A NUMBER */
PRINT$BYTE: PROCEDURE( N );
DECLARE N BYTE;
DECLARE ( V, D2, D3 ) BYTE;
V = N;
D3 = V MOD 10;
IF ( V := V / 10 ) <> 0 THEN DO;
D2 = V MOD 10;
IF ( V := V / 10 ) <> 0 THEN CALL PRINT$CHAR( '0' + V );
CALL PRINT$CHAR( '0' + D2 );
END;
CALL PRINT$CHAR( '0' + D3 );
END PRINT$BYTE;
/* PRINTS A FIXED LENGTH STRING */
PRINT$SUBSTRING: PROCEDURE( S$PTR, LEN );
DECLARE S$PTR ADDRESS, LEN BYTE, S BASED S$PTR ( MAX$REP )BYTE;
DECLARE S$POS BYTE;
DO S$POS = 0 TO LEN - 1;
CALL PRINT$CHAR( S( S$POS ) );
END;
END PRINT$SUBSTRING;
/* RETURNS THE LENGTH OF A $ TERMINATED STRING */
STR$LENGTH: PROCEDURE( S$PTR )BYTE;
DECLARE S$PTR ADDRESS, S BASED S$PTR ( MAX$REP )BYTE;
DECLARE RESULT BYTE;
RESULT = 0;
DO WHILE( S( RESULT ) <> '$' );
RESULT = RESULT + 1;
END;
RETURN RESULT;
END STR$LENGTH;
/* RETURNS THE LENGTH OF THE LONGEST REP-STRING IN S$PTR, */
LONGEST$REP$STRING: PROCEDURE( S$PTR )BYTE;
DECLARE S$PTR ADDRESS, S BASED S$PTR ( MAX$REP )BYTE;
DECLARE ( S$LEN, RESULT, S$POS, R$POS, I, FOUND ) BYTE;
RESULT = 0;
FOUND = FALSE;
S$LEN = STR$LENGTH( S$PTR );
S$POS = ( S$LEN / 2 ) - 1; /* IF ( S$LEN / 2 ) = 0, S$POS WILL BE 255 */
DO WHILE( NOT FOUND AND S$POS < 255 ); /* AS BYTE/ADDRESS ARE UNSIGNED */
/* CHECK THE POTENTIAL REP-STRING REPEATED A SUFFICIENT NUMBER */
/* OF TIMES (TRUNCATED IF NECESSARY) EQUALS THE ORIGINAL STRING */
FOUND = TRUE;
R$POS = S$POS + 1;
DO WHILE( FOUND AND R$POS < S$LEN AND FOUND );
I = 0;
DO WHILE( I <= S$POS AND R$POS < S$LEN AND FOUND );
FOUND = S( R$POS ) = S( I );
R$POS = R$POS + 1;
I = I + 1;
END;
END;
IF NOT FOUND THEN DO;
/* HAVEN'T FOUND A REP-STRING, TRY A SHORTER ONE */
S$POS = S$POS - 1; /* S$POS WILL BECOME 255 IF S$POS = 0 */
END;
END;
IF FOUND THEN DO;
RESULT = S$POS + 1;
END;
RETURN RESULT;
END LONGEST$REP$STRING;
DECLARE ( TEST$NUMBER, REP$STRING$LEN ) BYTE;
DECLARE TESTS ( 11 )ADDRESS;
TESTS( 0 ) = .'1001110011$';
TESTS( 1 ) = .'1110111011$';
TESTS( 2 ) = .'0010010010$';
TESTS( 3 ) = .'1010101010$';
TESTS( 4 ) = .'1111111111$';
TESTS( 5 ) = .'0100101101$';
TESTS( 6 ) = .'0100100$';
TESTS( 7 ) = .'101$';
TESTS( 8 ) = .'11$';
TESTS( 9 ) = .'00$';
TESTS( 10 ) = .'1$';
DO TEST$NUMBER = 0 TO LAST( TESTS );
REP$STRING$LEN = LONGEST$REP$STRING( TESTS( TEST$NUMBER ) );
CALL PRINT$STRING( TESTS( TEST$NUMBER ) );
IF REP$STRING$LEN = 0 THEN DO;
CALL PRINT$STRING( .': NO REP STRING$' );
END;
ELSE DO;
CALL PRINT$STRING( .': LONGEST REP STRING: $' );
CALL PRINT$SUBSTRING( TESTS( TEST$NUMBER ), REP$STRING$LEN );
END;
CALL PRINT$STRING( .( CR, LF, '$' ) );
END;
EOF- Output:
1001110011: LONGEST REP STRING: 10011 1110111011: LONGEST REP STRING: 1110 0010010010: LONGEST REP STRING: 001 1010101010: LONGEST REP STRING: 1010 1111111111: LONGEST REP STRING: 11111 0100101101: NO REP STRING 0100100: LONGEST REP STRING: 010 101: NO REP STRING 11: LONGEST REP STRING: 1 00: LONGEST REP STRING: 0 1: NO REP STRING
Prolog
Using SWI-Prolog 7 library(func), for some functional syntax.
:- use_module(library(func)).
%% Implementation logic:
test_for_repstring(String, (String, Result, Reps)) :-
( setof(Rep, repstring(String, Rep), Reps)
-> Result = 'no repstring'
; Result = 'repstrings', Reps = []
).
repstring(Codes, R) :-
RepLength = between(1) of (_//2) of length $ Codes,
length(R, RepLength),
phrase( (rep(R), prefix(~,R)),
Codes).
rep(X) --> X, X.
rep(X) --> X, rep(X).
%% Demonstration output:
test_strings([`1001110011`, `1110111011`, `0010010010`, `1010101010`,
`1111111111`, `0100101101`, `0100100`, `101`, `11`, `00`, `1`]).
report_repstring((S,Result,Reps)):-
format('~s -- ~w: ', [S, Result]),
foreach(member(R, Reps), format('~s, ', [R])), nl.
report_repstrings :-
Results = maplist(test_for_repstring) $ test_strings(~),
maplist(report_repstring, Results).
Output
?- report_repstrings. 1001110011 -- repstrings: 10011, 1110111011 -- repstrings: 1110, 0010010010 -- repstrings: 001, 1010101010 -- repstrings: 10, 1010, 1111111111 -- repstrings: 1, 11, 111, 1111, 11111, 0100101101 -- no repstring: 0100100 -- repstrings: 010, 101 -- no repstring: 11 -- repstrings: 1, 00 -- repstrings: 0, 1 -- no repstring: true.
PureBasic
a$="1001110011"+#CRLF$+"1110111011"+#CRLF$+"0010010010"+#CRLF$+"1010101010"+#CRLF$+"1111111111"+#CRLF$+
"0100101101"+#CRLF$+"0100100" +#CRLF$+"101" +#CRLF$+"11" +#CRLF$+"00" +#CRLF$+
"1" +#CRLF$
OpenConsole()
Procedure isRepStr(s1$,s2$)
If Int(Len(s1$)/Len(s2$))>=2 : ProcedureReturn isRepStr(s1$,s2$+s2$) : EndIf
If Len(s1$)>Len(s2$) : ProcedureReturn isRepStr(s1$,s2$+Left(s2$,Len(s1$)%Len(s2$))) : EndIf
If s1$=s2$ : ProcedureReturn #True : Else : ProcedureReturn #False : EndIf
EndProcedure
For k=1 To CountString(a$,#CRLF$)
s1$=StringField(a$,k,#CRLF$) : s2$=Left(s1$,Len(s1$)/2)
While Len(s2$)
r=isRepStr(s1$,s2$)
If Not r : s2$=Left(s2$,Len(s2$)-1) : Else : Break : EndIf
Wend
If Len(s2$) And r : PrintN(LSet(s1$,15,Chr(32))+#TAB$+"longest sequence: "+s2$) : EndIf
If Not Len(s2$) : PrintN(LSet(s1$,15,Chr(32))+#TAB$+"found nothing.") : EndIf
Next
Input()
- Output:
1001110011 longest sequence: 10011 1110111011 longest sequence: 1110 0010010010 longest sequence: 001 1010101010 longest sequence: 1010 1111111111 longest sequence: 11111 0100101101 found nothing. 0100100 longest sequence: 010 101 found nothing. 11 longest sequence: 1 00 longest sequence: 0 1 found nothing.
Python
Python: Procedural
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'))
- 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
>>> 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 []
>>>
And we could also express this in terms of itertools.cycle
'''Rep-strings'''
from itertools import (accumulate, chain, cycle, islice)
# repCycles :: String -> [String]
def repCycles(s):
'''Repeated sequences of characters in s.'''
n = len(s)
cs = list(s)
return [
x for x in
tail(inits(take(n // 2)(s)))
if cs == take(n)(cycle(x))
]
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Tests - longest cycle (if any) in each string.'''
print(
fTable('Longest cycles:\n')(repr)(
lambda xs: ''.join(xs[-1]) if xs else '(none)'
)(repCycles)([
'1001110011',
'1110111011',
'0010010010',
'1010101010',
'1111111111',
'0100101101',
'0100100',
'101',
'11',
'00',
'1',
])
)
# GENERIC -------------------------------------------------
# inits :: [a] -> [[a]]
def inits(xs):
'''all initial segments of xs, shortest first.'''
return accumulate(chain([[]], xs), lambda a, x: a + [x])
# tail :: [a] -> [a]
# tail :: Gen [a] -> [a]
def tail(xs):
'''The elements following the head of a
(non-empty) list or generator stream.'''
if isinstance(xs, list):
return xs[1:]
else:
list(islice(xs, 1)) # First item dropped.
return xs
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.'''
return lambda xs: (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
# OUTPUT FORMATTING ---------------------------------------
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function ->
fx display function ->
f -> value list -> tabular string.
'''
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
Longest cycles:
'1001110011' -> 10011
'1110111011' -> 1110
'0010010010' -> 001
'1010101010' -> 1010
'1111111111' -> 11111
'0100101101' -> (none)
'0100100' -> 010
'101' -> (none)
'11' -> 1
'00' -> 0
'1' -> (none)
Python: Regexp
This version, inspired by the Raku entry uses the regexp substitute where what the match is substituted with is returned by a function.
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)
- 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
Python: find
See David Zhang's solution to the same question posed on Stack Overflow.
Quackery
factors is defined at Factors of an integer.
[ false swap
dup size 1 > if
[ [] temp put
dup size factors
-1 split drop
witheach
[ 2dup split drop
dip [ over size swap / ]
dup temp replace
swap of over = if
[ drop not
temp share
conclude ] ]
temp release ] swap ] is rep$ ( $ --> $ b )
[ dup rep$ iff
[ say 'The shortest rep-string in "'
swap echo$
say '" is "' echo$
say '".' ]
else
[ say 'There is no rep-string for "'
nip echo$ say '".' ]
cr ] is task ( $ --> )- Output:
The shortest rep-string in "1001110011" is "10011". There is no rep-string for "1110111011". There is no rep-string for "0010010010". The shortest rep-string in "1010101010" is "10". The shortest rep-string in "1111111111" is "1". There is no rep-string for "0100101101". There is no rep-string for "0100100". There is no rep-string for "101". The shortest rep-string in "11" is "1". The shortest rep-string in "00" is "0". There is no rep-string for "1".
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")))
- 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
Raku
(formerly Perl 6)
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)";
}
}
- 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.
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)";
}
}
Refal
$ENTRY Go {
, ('1001110011') ('1110111011') ('0010010010')
('1010101010') ('1111111111') ('0100101101')
('0100100') ('101') ('11') ('00') ('1'): e.Tests
= <Each Show e.Tests>;
};
Each {
s.F = ;
s.F t.I e.R = <Mu s.F t.I> <Each s.F e.R>;
};
Show {
(e.S), <RepString e.S>: e.R = <Prout e.S ' => ' e.R>;
};
RepString {
() e.S = ;
(e.R) e.S, <Lengthen (e.R) e.S>: e.S e.X = e.R;
(e.R s.C) e.S = <RepString (e.R) e.S>;
e.S, <Lenw e.S>: s.L e.S,
<First <Div s.L 2> e.S>: (e.F) e.X
= <RepString (e.F) e.S>;
};
Lengthen {
(e.A) e.B, <Lenw e.A>: s.LA e.A,
<Lenw e.B>: s.LB e.B,
<Compare s.LA s.LB>: '-'
= <Lengthen (e.A e.A) e.B>;
(e.A) e.B, <Lenw e.B>: s.LB e.B,
<First s.LB e.A>: (e.FA) e.RA
= e.FA;
};- Output:
1001110011 => 10011 1110111011 => 1110 0010010010 => 001 1010101010 => 1010 1111111111 => 11111 0100101101 => 0100100 => 010 101 => 11 => 1 00 => 0 1 =>
REXX
version 1
/* 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
- 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
A check was added to validate if the strings are binary strings. The binary strings can be of any length.
/*REXX pgm determines if a string is a repString, it returns minimum length repString.*/
parse arg s /*get optional strings from the C.L. */
if s='' then s=1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1 45
/* [β] S not specified? Use defaults*/
do k=1 for words(s); _=word(s,k); w=length(_) /*process binary strings. */
say right(_,max(25,w)) repString(_) /*show repString & result.*/
end /*k*/ /* [β] the "result" may be negatory.*/
exit /*stick a fork in it, we're all done. */
/*ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ*/
repString: procedure; parse arg x; L=length(x); @rep=' rep string='
if \datatype(x,'B') then return " ***error*** string isn't a binary string."
h=L%2
do j=1 for L-1 while j<=h; $=left(x,j); $$=copies($,L)
if left($$,L)==x then return @rep left($,15) "[length" j']'
end /*j*/ /* [β] we have found a good repString.*/
return ' (no repetitions)' /*failure to find repString.*/
output when using the default binary strings for input:
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)
45 ***error*** string isn't a binary string.
Ring
# Project : Rep-string
test = ["1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"]
for n = 1 to len(test)
strend = ""
for m=1 to len(test[n])
strbegin = substr(test[n], 1, m)
strcut = right(test[n], len(test[n]) - m)
nr = substr(strcut, strbegin)
if nr=1 and len(test[n]) > 1
strend = strbegin
ok
next
if strend = ""
see "" + test[n] + " -> (none)" + nl
else
see "" + test[n] + " -> " + strend + nl
ok
nextOutput:
1001110011 -> 10011 1110111011 -> 1110 0010010010 -> 001 1010101010 -> 1010 1111111111 -> 11111 0100101101 -> 010 0100100 -> 010 101 -> (none) 11 -> 1 00 -> 0 1 -> (none)
RPL
βͺ DUP SIZE β in lin
βͺ ""
IF lin 1 > THEN
lin 2 / FLOOR 1 FOR lrep
in 1 lrep SUB DUP
DO OVER + UNTIL DUP SIZE lin β₯ END
IF 1 lin SUB in == THEN SWAP 0 βlrepβ STO END
DROP
-1 STEP
END
β« β« 'REPSTR' STO
βͺ { "1001110011" "1110111011" "0010010010" "1010101010" "1111111111" "0100101101" "0100100" "101" "11" "00" "1" }
{ } 1 3 PICK SIZE FOR j
OVER j GET REPSTR +
NEXT SWAP DROP
β« 'TASK' STO
- Output:
1: { "10011" "1110" "001" "1010" "11111" "" "010" "" "1" "0" "" }
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
- 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)
Rust
fn main() {
let strings = vec![
String::from("1001110011"),
String::from("1110111011"),
String::from("0010010010"),
String::from("1010101010"),
String::from("1111111111"),
String::from("0100101101"),
String::from("0100100"),
String::from("101"),
String::from("11"),
String::from("00"),
String::from("1"),
];
for string in strings {
match rep_string(&string) {
Some(rep_string) => println!(
"Longuest rep-string for '{}' is '{}' ({} chars)",
string,
rep_string,
rep_string.len(),
),
None => println!("No rep-string found for '{}'", string),
};
}
}
fn rep_string(string: &str) -> Option<&str> {
let index = string.len() / 2;
for split_index in (1..=index).rev() {
let mut is_rep_string = true;
let (first, last) = string.split_at(split_index);
let inter = last.chars().collect::<Vec<char>>();
let mut iter = inter.chunks_exact(split_index);
for chunk in iter.by_ref() {
if first != chunk.iter().collect::<String>() {
is_rep_string = false;
break;
}
}
let rmnd = iter.remainder().iter().collect::<String>();
// Check that the remainder starts with the rep-string
if !first.starts_with(rmnd.as_str()) {
is_rep_string = false;
}
if is_rep_string {
return Some(first);
}
}
None
}
#[cfg(test)]
mod tests {
use super::rep_string;
use std::collections::HashMap;
#[test]
fn test_rep_string() {
let mut results = HashMap::new();
results.insert(String::from("1001110011"), Some("10011"));
results.insert(String::from("1110111011"), Some("1110"));
results.insert(String::from("0010010010"), Some("001"));
results.insert(String::from("1010101010"), Some("1010"));
results.insert(String::from("1111111111"), Some("11111"));
results.insert(String::from("0100101101"), None);
results.insert(String::from("0100100"), Some("010"));
results.insert(String::from("101"), None);
results.insert(String::from("11"), Some("1"));
results.insert(String::from("00"), Some("0"));
results.insert(String::from("1"), None);
for (input, expected) in results {
assert_eq!(expected, rep_string(&input));
}
}
}
Scala
object RepString extends App {
def repsOf(s: String) = s.trim match {
case s if s.length < 2 => Nil
case s => (1 to (s.length/2)).map(s take _)
.filter(_ * s.length take s.length equals s)
}
val tests = Array(
"1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
)
def printReps(s: String) = repsOf(s) match {
case Nil => s+": NO"
case r => s+": YES ("+r.mkString(", ")+")"
}
val todo = if (args.length > 0) args else tests
todo.map(printReps).foreach(println)
}
- Output:
1001110011: YES (10011) 1110111011: YES (1110) 0010010010: YES (001) 1010101010: YES (10, 1010) 1111111111: YES (1, 11, 111, 1111, 11111) 0100101101: NO 0100100: YES (010) 101: NO 11: YES (1) 00: YES (0) 1: NO
Seed7
$ include "seed7_05.s7i";
const func integer: repeatLength (in string: text) is func
result
var integer: length is 0;
local
var integer: pos is 0;
begin
for pos range succ(length(text) div 2) downto 1 until length <> 0 do
if startsWith(text, text[pos ..]) then
length := pred(pos);
end if;
end for;
end func;
const proc: main is func
local
var string: line is "";
var integer: length is 0;
begin
for line range [] ("1001110011", "1110111011", "0010010010", "1010101010",
"1111111111", "0100101101", "0100100", "101", "11", "00", "1") do
length := repeatLength(line);
if length = 0 then
writeln("No rep-string for " <& literal(line));
else
writeln("Longest rep-string for " <& literal(line) <& ": " <& literal(line[.. length]));
end if;
end for;
end func;- Output:
Longest rep-string for "1001110011": "10011" Longest rep-string for "1110111011": "1110" Longest rep-string for "0010010010": "001" Longest rep-string for "1010101010": "1010" Longest rep-string for "1111111111": "11111" No rep-string for "0100101101" Longest rep-string for "0100100": "010" No rep-string for "101" Longest rep-string for "11": "1" Longest rep-string for "00": "0" No rep-string for "1"
SETL
program repstring;
tests := [
"1001110011", "1110111011", "0010010010", "1010101010",
"1111111111", "0100101101", "0100100", "101", "11", "00", "1"
];
loop for test in tests do
print(test + ": " + str repstrings(test));
end loop;
proc repstrings(s);
return {
s(..l) : l in [1..#s div 2]
| (s(..l)*(#s div l+1))(..#s) = s
};
end proc;
end program;- Output:
1001110011: {'10011'}
1110111011: {'1110'}
0010010010: {'001'}
1010101010: {'10' '1010'}
1111111111: {'1' '11' '111' '1111' '11111'}
0100101101: {}
0100100: {'010'}
101: {}
11: {'1'}
00: {'0'}
1: {}
Sidef
var arr = <1001110011 1110111011
0010010010 1010101010
1111111111 0100101101
0100100 101 11 00 1>;
arr.each { |n|
if (var m = /^(.+)\1+(.*$)(?(?{ substr($1, 0, length $2) eq $2 })|(?!))/.match(n)) {
var i = m[0].len;
say (n.substr(0, i),
n.substr(i, i).tr('01', 'ππ'),
n.substr(i*2));
} else {
say "#{n} (no repeat)";
}
}
- Output:
10011πππππ 1110ππππ11 001πππ0010 1010ππππ10 11111πππππ 0100101101 (no repeat) 010πππ0 101 (no repeat) 1π 0π 1 (no repeat)
Snobol4
* Rep-string
strings = "1001110011 1110111011 0010010010 1010101010 1111111111 0100101101 0100100 101 11 00 1 "
pat1 = (len(1) $ fc breakx(*fc)) $ x *x (arbno(*x) (rpos(0) | rem $ y *?(x ? y)))
getstring
strings ? (break(" ") . rs len(1)) = :f(end)
rs ? pat1 :s(yes)
output = rs " is not a rep-string -> n/a" :(getstring)
yes
output = rs " has shortest rep-string value of -> " x
:(getstring)
end- Output:
1001110011 has shortest rep-string value of -> 10011 1110111011 has shortest rep-string value of -> 1110 0010010010 has shortest rep-string value of -> 001 1010101010 has shortest rep-string value of -> 10 1111111111 has shortest rep-string value of -> 1 0100101101 is not a rep-string -> n/a 0100100 has shortest rep-string value of -> 010 101 is not a rep-string -> n/a 11 has shortest rep-string value of -> 1 00 has shortest rep-string value of -> 0 1 is not a rep-string -> n/a
Swift
import Foundation
func repString(_ input: String) -> [String] {
return (1..<(1 + input.count / 2)).compactMap({x -> String? in
let i = input.index(input.startIndex, offsetBy: x)
return input.hasPrefix(input[i...]) ? String(input.prefix(x)) : nil
})
}
let testCases = """
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1
""".components(separatedBy: "\n")
for testCase in testCases {
print("\(testCase) has reps: \(repString(testCase))")
}
- Output:
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: []
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"
}
Demonstrating:
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]
}
}
- 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
UNIX Shell
is_repeated() {
local str=$1 len rep part
for (( len = ${#str} / 2; len > 0; len-- )); do
part=${str:0:len}
rep=""
while (( ${#rep} < ${#str} )); do
rep+=$part
done
if [[ ${rep:0:${#str}} == $str ]] && (( $len < ${#str} )); then
echo "$part"
return 0
fi
done
return 1
}
while read test; do
if part=$( is_repeated "$test" ); then
echo "$test is composed of $part repeated"
else
echo "$test is not a repeated string"
fi
done <<END_TESTS
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1
END_TESTS
- Output:
1001110011 is composed of 10011 repeated 1110111011 is composed of 1110 repeated 0010010010 is composed of 001 repeated 1010101010 is composed of 1010 repeated 1111111111 is composed of 11111 repeated 0100101101 is not a repeated string 0100100 is composed of 010 repeated 101 is not a repeated string 11 is composed of 1 repeated 00 is composed of 0 repeated 1 is not a repeated string
VBScript
Function rep_string(s)
max_len = Int(Len(s)/2)
tmp = ""
If max_len = 0 Then
rep_string = "No Repeating String"
Exit Function
End If
For i = 1 To max_len
If InStr(i+1,s,tmp & Mid(s,i,1))Then
tmp = tmp & Mid(s,i,1)
Else
Exit For
End If
Next
Do While Len(tmp) > 0
If Mid(s,Len(tmp)+1,Len(tmp)) = tmp Then
rep_string = tmp
Exit Do
Else
tmp = Mid(tmp,1,Len(tmp)-1)
End If
Loop
If Len(tmp) > 0 Then
rep_string = tmp
Else
rep_string = "No Repeating String"
End If
End Function
'testing the function
arr = Array("1001110011","1110111011","0010010010","1010101010",_
"1111111111","0100101101","0100100","101","11","00","1")
For n = 0 To UBound(arr)
WScript.StdOut.Write arr(n) & ": " & rep_string(arr(n))
WScript.StdOut.WriteLine
Next
- Output:
1001110011: 10011 1110111011: 1110 0010010010: 001 1010101010: 1010 1111111111: 11111 0100101101: 010 0100100: 010 101: No Repeating String 11: 1 00: 0 1: No Repeating String
V (Vlang)
fn rep(s string) int {
for x := s.len / 2; x > 0; x-- {
if s.starts_with(s[x..]) {
return x
}
}
return 0
}
const m = '
1001110011
1110111011
0010010010
1010101010
1111111111
0100101101
0100100
101
11
00
1'
fn main() {
for s in m.fields() {
n := rep(s)
if n > 0 {
println("$s $n rep-string ${s[..n]}")
} else {
println("$s not a rep-string")
}
}
}- 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
Wren
import "./fmt" for Fmt
var repString = Fn.new { |s|
var reps = []
if (s.count < 2) return reps
for (c in s) if (c != "0" && c != "1") Fiber.abort("Argument is not a binary string.")
var size = s.count
for (len in 1..(size/2).floor) {
var t = s[0...len]
var n = (size/len).floor
var r = size % len
var u = t * n + t[0...r]
if (u == s) reps.add(t)
}
return reps
}
var strings = [
"1001110011",
"1110111011",
"0010010010",
"1010101010",
"1111111111",
"0100101101",
"0100100",
"101",
"11",
"00",
"1"
]
System.print("The (longest) rep-strings are:\n")
for (s in strings) {
var reps = repString.call(s)
var t = (reps.count > 0) ? reps[-1] : "Not a rep-string"
Fmt.print("$10s -> $s", s, t)
}
- Output:
The (longest) rep-strings are:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> Not a rep-string
0100100 -> 010
101 -> Not a rep-string
11 -> 1
00 -> 0
1 -> Not a rep-string
XPL0
include xpllib; \for StrLen, StrFind and Print
func RepStr(Str);
char Str;
int SL;
[if Str(0) = 0 then return 0;
SL:= StrLen(Str)/2;
while SL > 0 do
[if StrFind(Str, Str+SL) = Str then
return SL;
SL:= SL-1;
];
return 0;
];
int Strs, I, N;
char PS;
[Strs:= ["1001110011", "1110111011", "0010010010", "1111111111",
"0100101101", "0100100", "101", "11", "00", "1"];
for I:= 0 to 10-1 do
[N:= RepStr(Strs(I));
PS:= "^"%s^" = rep-string ^"%1.0s^"\n";
PS(22):= N+^0; \ 8-)
if N # 0 then
Print(PS, Strs(I), Strs(I))
else
Print("^"%s^" = not a rep-string\n", Strs(I));
];
]- Output:
"1001110011" = rep-string "10011" "1110111011" = rep-string "1110" "0010010010" = rep-string "001" "1111111111" = rep-string "11111" "0100101101" = not a rep-string "0100100" = rep-string "010" "101" = not a rep-string "11" = rep-string "1" "00" = rep-string "0" "1" = not a rep-string
Yabasic
data "1001110011", "1110111011", "0010010010", "1010101010", "1111111111", "0100101101", "0100100", "101", "11", "00", "1", ""
sub rep$(c$, n)
local r$, i
for i = 1 to n
r$ = r$ + c$
next
return r$
end sub
do
read p$ : if p$ = "" break
b$ = "" : l = len(p$) : m = int(l / 2)
for i = m to 1 step -1
t$ = left$(p$, i)
s$ = rep$(t$, l / i + 1)
if p$ = left$(s$, l) b$ = t$ : break
next
if b$ = "" then
print p$, " is not a repeated string"
else
print p$, " is composed of ", b$, " repeated"
end if
loopzkl
fcn repString(s){
foreach n in ([s.len()/2+1..1,-1]){
Walker.cycle(s[0,n]).pump(s.len(),String) :
if(_==s and n*2<=s.len()) return(n);
}
return(False)
}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)
}words:=("1001110011 1110111011 0010010010 1010101010 "
"1111111111 0100101101 0100100 101 11 00 1").split(" ");
foreach w in (words){
if(not n:=repString2(w)) "No repeat in ".println(w);
else [0..*,n].tweak('wrap(z){ if(s:=w[z,n]) s else Void.Stop })
.walk().concat(" ").println();
}- 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
Categories:
- Programming Tasks
- Solutions by Programming Task
- 11l
- ABC
- Action!
- Ada
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- BaCon
- BASIC
- Applesoft BASIC
- BCPL
- Bracmat
- BQN
- C
- C sharp
- C++
- Clojure
- CLU
- Common Lisp
- Crystal
- D
- Delphi
- System.SysUtils
- DuckDB
- Dyalect
- EasyLang
- EchoLisp
- Ed
- Elixir
- Excel
- F Sharp
- Factor
- Forth
- FreeBASIC
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- LFE
- Maple
- Mathematica
- Wolfram Language
- Miranda
- Modula-2
- NetRexx
- NGS
- Nim
- Objeck
- Oforth
- PARI/GP
- Perl
- Phix
- Phixmonti
- Picat
- PicoLisp
- PL/I
- PL/I examples needing attention
- Examples needing attention
- PL/M
- Prolog
- PureBasic
- Python
- Quackery
- Racket
- Raku
- Refal
- REXX
- Ring
- RPL
- Ruby
- Rust
- Scala
- Seed7
- SETL
- Sidef
- Snobol4
- Swift
- Tcl
- UNIX Shell
- VBScript
- V (Vlang)
- Wren
- Wren-fmt
- XPL0
- Yabasic
- Zkl