Rep-string: Difference between revisions
m
→{{header|ABC}}: Added main program
(Added F# version) |
m (→{{header|ABC}}: Added main program) |
||
| (93 intermediate revisions by 38 users not shown) | |||
Line 2:
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
Note that the requirement for having the repeat occur two or more times means that the repeating unit is
Line 27:
</dl>
* Show your output on this page.
{{Template:Strings}}
<br><br>
=={{header|11l}}==
{{trans|Python: Functional}}
<syntaxhighlight lang="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)))</syntaxhighlight>
{{out}}
<pre>
'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 []
</pre>
=={{header|ABC}}==
<syntaxhighlight lang="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 /
</syntaxhighlight>
{{out}}
<pre>1001110011: {"10011"}
1110111011: {"1110"}
0010010010: {"001"}
1010101010: {"10"; "1010"}
1111111111: {"1"; "11"; "111"; "1111"; "11111"}
0100101101: {}
0100100: {"010"}
101: {}
11: {"1"}
00: {"0"}
1: {}</pre>
=={{header|Action!}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Rep-string.png Screenshot from Atari 8-bit computer]
<pre>
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
</pre>
=={{header|Ada}}==
<
procedure Rep_String is
Line 61 ⟶ 216:
Ada.Text_IO.Put_Line("Longest rep-string for """& X &""": """& Y &"""");
end if;
end Rep_String;</
{{out}}
Line 90 ⟶ 245:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
# the input string is not validated to contain only "0" and "1" characters #
PROC longest rep string = ( STRING input )STRING:
Line 157 ⟶ 312:
)
OD
)</
{{out}}
<pre>1001110011: longest rep string: "10011"
1110111011: longest rep string: "1110"
0010010010: longest rep string: "001"
Line 170 ⟶ 324:
11: longest rep string: "1"
00: longest rep string: "0"
1: no rep string</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
This function returns a list of all possible repeated substrings.
It returns the empty list if there are none.
<syntaxhighlight lang="apl">rep ← ⊢ (⊢(/⍨)(⊂⊣)≡¨(≢⊣)⍴¨⊢) ⍳∘(⌊0.5×≢)↑¨⊂</syntaxhighlight>
{{out}}
<pre> 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'
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{Out}}
<pre>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)</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">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 ")"]
]</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|AutoHotkey}}==
{{works with|AutoHotkey 1.1}}
<
, "1111111111", "0100101101", "0100100", "101", "11", "00", "1"]
for k, v in In
Line 192 ⟶ 663:
}
return "N/A"
}</
{{Out}}
<pre>10011 1001110011
Line 205 ⟶ 676:
0 00
N/A 1</pre>
=={{header|BaCon}}==
<syntaxhighlight lang="freebasic">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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|BASIC}}==
<syntaxhighlight lang="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",""</syntaxhighlight>
{{out}}
<pre>1001110011: 10011
1110111011: 1110
0010010010: 001
1010101010: 1010
1111111111: 11111
0100101101: none
0100100: 010
101: none
11: 1
00: 0
1: none</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="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")
$)</syntaxhighlight>
{{out}}
<pre>1001110011: 10011
1110111011: 1110
0010010010: 001
1010101010: 1010
1111111111: 11111
0100101101: none
0100100: 010
101: none
11: 1
00: 0
1: none</pre>
=={{header|Bracmat}}==
<
= reps L x y
. ( reps
Line 242 ⟶ 839:
& rep-string$00
& rep-string$1
);</
{{Out}}
<pre>1001110011 : 10011
Line 255 ⟶ 852:
00 : 0
1 is not a rep-string</pre>
=={{header|BQN}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>"1001110011:⟨ ""10011"" ⟩
1110111011:⟨ ""1110"" ⟩
0010010010:⟨ ""001"" ⟩
1010101010:⟨ ""10"" ""1010"" ⟩
1111111111:⟨ ""1"" ""11"" ""111"" ""1111"" ""11111"" ⟩
0100101101:⟨⟩
0100100:⟨ ""010"" ⟩
101:⟨⟩
11:⟨ ""1"" ⟩
00:⟨ ""0"" ⟩
1:⟨⟩
"</pre>
=={{header|C}}==
===Longest substring ===
<syntaxhighlight lang="c">
#include <stdio.h>
#include <string.h>
Line 292 ⟶ 917:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 305 ⟶ 930:
"00" = rep-string "0"
"1" = not a rep-string
</pre>
===shortest substring===
<syntaxhighlight lang="c">
// 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;
}
</syntaxhighlight>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="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";
}
}
</syntaxhighlight>
{{out}}
<pre>
1001110011 : 10011
1110111011 : 1110
0010010010 : 001
1010101010 : 1010
1111111111 : 11111
0100101101 : none
0100100 : 010
101 : none
11 : 1
00 : 0
1 : none
0100101 : none
</pre>
=={{header|C++}}==
<
#include <vector>
#include <boost/regex.hpp>
Line 343 ⟶ 1,050:
}
return 0 ;
}</
{{out}}
<pre>1001110011 is a rep string! Here is a repeating string:
Line 364 ⟶ 1,071:
0
1 is no rep string!</pre>
===Without external libraries===
<syntaxhighlight lang="c++">
#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;
}
}
</syntaxhighlight>
{{ out }}
<pre>
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
</pre>
=={{header|Clojure}}==
<syntaxhighlight lang="lisp">(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)))</syntaxhighlight>
{{out}}
<syntaxhighlight lang="lisp">
(def test-strings ["1001110011"
"1110111011"
"0010010010"
"1010101010"
"1111111111"
"0100101101"
"0100100"
"101"
"11"
"00"
"1"])
(map (juxt identity rep-string) test-strings)
</syntaxhighlight>
<pre>
(["1001110011" true]
["1110111011" true]
["0010010010" true]
["1010101010" true]
["1111111111" true]
["0100101101" nil]
["0100100" true]
["101" nil]
["11" true]
["00" true]
["1" nil])
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>1001110011: <10011>
1110111011: <1110>
0010010010: <001>
1010101010: <1010> <10>
1111111111: <11111> <1111> <111> <11> <1>
0100101101:
0100100: <010>
101:
11: <1>
00: <0>
1:</pre>
=={{header|Common Lisp}}==
<
(ql:quickload :alexandria)
(defun rep-stringv (a-str &optional (max-rotation (floor (/ (length a-str) 2))))
Line 385 ⟶ 1,230:
;; Recurse function reducing length of rotation.
(t (rep-stringv a-str (1- max-rotation)))))
</syntaxhighlight>
{{out}}
<
(setf test-strings '("1001110011"
"1110111011"
Line 403 ⟶ 1,248:
(loop for item in test-strings
collecting (cons item (rep-stringv item)))
</syntaxhighlight>
<pre>
(("1001110011" . "10011") ("1110111011" . "1110") ("0010010010" . "001")
Line 410 ⟶ 1,255:
("101" . "Not a repeating string") ("11" . "1") ("00" . "0")
("1" . "Not a repeating string"))
</pre>
=={{header|Crystal}}==
{{trans|Go}}
<syntaxhighlight lang="ruby">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
</syntaxhighlight>
{{out}}
<pre>
"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
</pre>
=={{header|D}}==
Two different algorithms. The second is from the
<
std.ascii, std.typecons;
Line 457 ⟶ 1,352:
writefln("%(%s %)", w.chunks(r1));
}
}</
{{out}}
<pre>10011 10011
Line 470 ⟶ 1,365:
0 0
1 (no repeat)</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|Go}}
<syntaxhighlight lang="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.</syntaxhighlight>
=={{header|Dyalect}}==
{{trans|Go}}
<syntaxhighlight lang="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")
}
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
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
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(lib 'list) ;; list-rotate
Line 491 ⟶ 1,519:
'too-short-no-rep))
</syntaxhighlight>
{{out}}
<
(define strings '["1001110011" "1110111011" "0010010010" "1010101010"
"1111111111" "0100101101" "0100100" "101" "11" "00" "1"])
Line 514 ⟶ 1,542:
"00" "0"
"1" too-short-no-rep
</syntaxhighlight>
=={{header|Elixir}}==
<
def find(""), do: IO.puts "String was empty (no repetition)"
def find(str) do
Line 545 ⟶ 1,573:
1)
Enum.each(strs, fn str -> Rep_string.find(str) end)</
{{out}}
Line 582 ⟶ 1,610:
(no repetition)
</pre>
=={{header|Excel}}==
===LAMBDA===
Binding the following lambda expressions to the names REPCYCLES and TAKECYCLESTRING in the Excel Workbook Name Manager:
(See [https://www.microsoft.com/en-us/research/blog/lambda-the-ultimatae-excel-worksheet-function/ LAMBDA: The ultimate Excel worksheet function])
{{Works with|Office 365 betas 2021}}
<syntaxhighlight lang="lisp">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
)
)
)
)</syntaxhighlight>
And also assuming the following generic bindings in the Name Manager:
<syntaxhighlight lang="lisp">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()
)
)</syntaxhighlight>
{{Out}}
{| class="wikitable"
|-
|||style="text-align:right; font-family:serif; font-style:italic; font-size:120%;"|fx
! colspan="2" style="text-align:left; vertical-align: bottom; font-family:Arial, Helvetica, sans-serif !important;"|=LASTCOL(REPCYCLES(A2))
|- style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff;"
|
| A
| B
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 1
| style="text-align:right; font-weight:bold" | String
| style="text-align:left; font-weight:bold" | Longest cycle, if any
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 2
| style="text-align:right; font-weight:bold" | 1001110011
| style="text-align:left; background-color:#cbcefb;" | 10011
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 3
| style="text-align:right; font-weight:bold" | 1110111011
| style="text-align:left;" | 1110
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 4
| style="text-align:right; font-weight:bold" | 0010010010
| style="text-align:left;" | 001
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 5
| style="text-align:right; font-weight:bold" | 1010101010
| style="text-align:left;" | 1010
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 6
| style="text-align:right; font-weight:bold" | 1111111111
| style="text-align:left;" | 11111
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 7
| style="text-align:right; font-weight:bold" | 0100101101
| style="text-align:left;" | #N/A
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 8
| style="text-align:right; font-weight:bold" | 0100100
| style="text-align:left;" | 010
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 9
| style="text-align:right; font-weight:bold" | 101
| style="text-align:left;" | #N/A
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 10
| style="text-align:right; font-weight:bold" | 11
| style="text-align:left;" | 1
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 11
| style="text-align:right; font-weight:bold" | 00
| style="text-align:left;" | 0
|- style="text-align:right;"
| style="text-align:center; font-family:Arial, Helvetica, sans-serif !important; background-color:#000000; color:#ffffff" | 12
| style="text-align:right; font-weight:bold" | 1
| style="text-align:left;" | #N/A
|}
=={{header|F_Sharp|F#}}==
<
let getPrefix n (s : string) = s.Substring(0,n)
Line 618 ⟶ 1,794:
match repPrefixOf s with | None -> s + ": NO" | Some(p) -> s + ": YES ("+ p + ")")
|> List.iter (printfn "%s")
0</
{{out}}
<pre>Testing for rep-string (and showing the longest repeated prefix in case):
Line 632 ⟶ 1,808:
00: YES (0)
1: NO</pre>
=={{header|Factor}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Forth}}==
{{trans|Python}}
{{works with|GNU Forth}}
<
2dup dup >r r@ 2/ /string
begin 2over 2over string-prefix? 0= over r@ < and while -1 /string repeat
Line 656 ⟶ 1,865:
s" 11" test
s" 00" test
s" 1" test ;</
{{out}}
<
1001110011 has 10011 as repeating substring
1110111011 has 1110 as repeating substring
Line 670 ⟶ 1,879:
00 has 0 as repeating substring
1 has no repeating substring
ok</
=={{header|FreeBASIC}}==
{{trans|Yabasic}}
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 711 ⟶ 1,970:
}
}
}</
{{out}}
<pre>
Line 728 ⟶ 1,987:
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.List (inits, maximumBy)
import Data.
repstring :: String -> Maybe String
Line 735 ⟶ 1,994:
repstring [] = Nothing
-- strings with only one character are not rep strings
repstring
repstring xs
main :: IO ()
main =
[ "1001110011",
"0010010010",
"0100100",
"101",
"11",
"00",
"1"
]
process = fromMaybe "Not a rep string" . repstring
processIO xs = do
putStr (xs <> ": ")
putStrLn $ process xs</syntaxhighlight>
{{Out}}
<pre>1001110011: 10011
1110111011: 1110
0010010010: 001
Line 788 ⟶ 2,054:
11: 1
00: 0
1: Not a rep string</pre>
Or, alternatively:
<syntaxhighlight lang="haskell">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</syntaxhighlight>
{{Out}}
<pre>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</pre>
=={{header|Icon}} and {{header|Unicon}}==
Line 795 ⟶ 2,129:
The following works in both languages.
<
every write(s := !A,": ",(repString(s) | "Not a rep string!")\1)
end
Line 808 ⟶ 2,142:
while *s1 < n do s1 ||:= s2
return s1[1+:n]
end</
{{Out}}
Line 828 ⟶ 2,162:
Here's a test:
<
rep=: $@] $ $
isRepStr=: +./@((] -: rep)"0 1~ replengths)</
Example use:
<
1
Tests=: noun define
Line 851 ⟶ 2,185:
)
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:
<
With the above examples:
<
5
4
Line 869 ⟶ 2,203:
1
1</
Here, the "non-str-rep" cases are indicated by an empty list of prefix lengths.
=={{header|Java}}==
<
static final String[] input = {"1001110011", "1110111011", "0010010010",
Line 903 ⟶ 2,237:
return "none";
}
}</
{{Out}}
Line 918 ⟶ 2,252:
1 : none
0100101 : none</pre>
Alternative version avoiding the use of 'goto'
<syntaxhighlight lang="java">
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;
}
}
</syntaxhighlight>
{{ out }}
<pre>
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
</pre>
=={{header|JavaScript}}==
===ES6===
<syntaxhighlight lang="javascript">(() => {
'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();
})();</syntaxhighlight>
{{Out}}
<pre>Longest cycles:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> (none)
0100100 -> 010
101 -> (none)
11 -> 1
00 -> 0
1 -> (none)</pre>
=={{header|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.
<
# if self is a rep-string then return [n, prefix]
# where n is the number of full occurrences of prefix
Line 941 ⟶ 2,489:
| select( .[0] > 1 ) ]
;
</syntaxhighlight>
'''Example''':
<
(
"1001110011",
Line 959 ⟶ 2,507:
;
test</
{{Out}}
<
{"1001110011":[[2,"10011"]]}
{"1110111011":[[2,"1110"]]}
Line 972 ⟶ 2,520:
{"11":[[2,"1"]]}
{"00":[[2,"0"]]}
{"1":[]}</
=={{header|Julia}}==
<tt>
<syntaxhighlight lang="julia">function repstring(r::AbstractString)
n = length(r)
replst =
for m in 1:
s = r[1:chr2ind(r, m)]
if (s ^
push!(replst, s)
end
Line 988 ⟶ 2,536:
end
tests =
"
"\u2200\u2203\u2200\u2203\u2200\u2203\u2200\u2203"]
for r in tests
replst =
else
println("$r is a rep-string of ", join(replst, ", "), ".")
end
end</syntaxhighlight>
{{out}}
<pre> 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 ∀∃, ∀∃∀∃.</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// 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"}")
}
}</syntaxhighlight>
{{out}}
<pre>
The (longest) rep-strings are:
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 ->
0100100 -> 010
00 -> 0
1 -> Not a rep-string
</pre>
Line 1,033 ⟶ 2,623:
The heavy lifting:
<
(defun get-reps (text)
(lists:filtermap
Line 1,047 ⟶ 2,637:
(1 head)
(_ '()))))
</syntaxhighlight>
Displaying the results:
<
(defun report
((`#(,text ()))
Line 1,062 ⟶ 2,652:
(lists:zip data (lists:map #'get-reps/1 data)))
'ok))
</syntaxhighlight>
Running the code:
Line 1,095 ⟶ 2,685:
=={{header|Maple}}==
The built-in <code>Period</code> command in the <code>StringTools</code> package computes the length of the longest repeated prefix.
<
local per := StringTools:-Period( s );
if 2 * per <= length( s ) then
Line 1,102 ⟶ 2,692:
false, ""
end if
end proc:</
For the given set of test strings, we can generate the following output.
<syntaxhighlight lang="maple">
> Test := ["1001110011", "1110111011", "0010010010", "1010101010", "1111111111", \
"0100101101", "0100100", "101", "11", "00", "1"]:
Line 1,122 ⟶ 2,712:
1 false
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Mathematica is based on pattern-based matching, so this is very easily implemented:
<
Trying it out for the test-strings:
<syntaxhighlight lang="text">str={"1001110011","1110111011","0010010010","1010101010","1111111111","0100101101","0100100","101","11","00","1"};
{#,RepStringQ[#]}&/@str//Grid</
{{out}}
<pre>1001110011 {10011}
Line 1,144 ⟶ 2,734:
It outputs all the possibilities for a rep-string,
if there is no rep-string it will show an empty list {}.
=={{header|Miranda}}==
<syntaxhighlight lang="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))</syntaxhighlight>
{{out}}
<pre>1001110011: ["10011"]
1110111011: ["1110"]
0010010010: ["001"]
1010101010: ["10","1010"]
1111111111: ["1","11","111","1111","11111"]
0100101101: []
0100100: ["010"]
101: []
11: ["1"]
00: ["0"]
1: []</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">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.</syntaxhighlight>
{{out}}
<pre>1001110011: 10011
1110111011: 1110
0010010010: 001
1010101010: 1010
1111111111: 11111
0100101101:
0100100: 010
101:
11: 1
00: 0
1:</pre>
=={{header|NetRexx}}==
{{trans|REXX}}
<
options replace format comments java crossref symbols nobinary
Line 1,208 ⟶ 2,902:
end w_
return
</syntaxhighlight>
{{out}}
<pre>
Line 1,226 ⟶ 2,920:
=={{header|NGS}}==
{{trans|Python}}
<
'1001110011'
'1110111011'
Line 1,247 ⟶ 2,941:
echo("${test} ${if r "has repetition of length ${r} (i.e. ${test[0..r]})" "is not a rep-string"}")
})
}</
{{out}}<pre>1001110011 has repetition of length 5 (i.e. 10011)
1110111011 has repetition of length 4 (i.e. 1110)
Line 1,262 ⟶ 2,956:
=={{header|Nim}}==
{{trans|Python}}
<
proc isRepeated(text: string): int =
for x in countdown(text.len div 2, 0):
if text.startsWith(text[x..text.high]): return x
Line 1,283 ⟶ 2,977:
let ln = isRepeated(line)
echo "'", line, "' has a repetition length of ", ln, " i.e ",
(if ln > 0: "'" & line[0 ..
{{Out}}
<pre>'1001110011' has a repetition length of 5 i.e '10011'
Line 1,298 ⟶ 2,992:
=={{header|Objeck}}==
<
function : Main(args : String[]) ~ Nil {
strings := ["1001110011", "1110111011", "0010010010", "1111111111",
Line 1,359 ⟶ 3,053:
return true;
}
}</
Output:
Line 1,379 ⟶ 3,073:
Returns null if no rep string.
<
| 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 ;</
{{Out}}
Line 1,394 ⟶ 3,088:
=={{header|PARI/GP}}==
<
v=["1001110011","1110111011","0010010010","1010101010","1111111111","0100101101","0100100","101","11","00","1"];
for(i=1,#v,print(v[i]" "rep(Vec(v[i]))))</
{{out}}
<pre>1001110011 5
Line 1,411 ⟶ 3,105:
=={{header|Perl}}==
<
print "$_\n";
if (/^(.+)\1+(.*$)(?(?{ substr($1, 0, length $2) eq $2 })|(?!))/) {
Line 1,418 ⟶ 3,112:
print " (no repeat)\n\n";
}
}</
{{out}}
<pre>1001110011
Line 1,453 ⟶ 3,147:
(no repeat)</pre>
=={{header|
{{trans|Julia}}
Shows all possible repeated sub-strings, as Julia, but in the output style of Perl/Elixir
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">list_reps</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">replist</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">r</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">replist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">replist</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">replist</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"1001110011"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1110111011"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"0010010010"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1010101010"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1111111111"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"0100101101"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"0100100"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"101"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"11"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"00"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">replist</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">list_reps</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">replist</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"not a rep-string.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">replist</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">rj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">replist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span>
<span style="color: #7060A8;">pad</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rj</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">pad</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rj</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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.
</pre>
=={{header|Phixmonti}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>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 ===</pre>
=={{header|Picat}}==
<syntaxhighlight lang="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,_). </syntaxhighlight>
{{out}}
<pre>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]</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="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 ) ) ) )</syntaxhighlight>
Test:
<syntaxhighlight lang="picolisp">(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"))</syntaxhighlight>
=={{header|PL/I}}==
{{Incorrect|PL/I|"0100101101" is not a rep-string.}}
<
declare s bit (10) varying;
declare (i, k) fixed binary;
Line 1,518 ⟶ 3,390:
end;
end rep;</
{{Out}}
<pre>
Line 1,532 ⟶ 3,404:
00 is a rep-string containing 0
1 is not a rep-string
</pre>
=={{header|PL/M}}==
<syntaxhighlight lang="plmi">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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 1,538 ⟶ 3,533:
Using SWI-Prolog 7 library(func), for some functional syntax.
<
%% Implementation logic:
Line 1,569 ⟶ 3,564:
report_repstrings :-
Results = maplist(test_for_repstring) $ test_strings(~),
maplist(report_repstring, Results).</
Output
Line 1,588 ⟶ 3,583:
=={{header|PureBasic}}==
<
"0100101101"+#CRLF$+"0100100" +#CRLF$+"101" +#CRLF$+"11" +#CRLF$+"00" +#CRLF$+
"1" +#CRLF$
Procedure isRepStr(s1$,s2$)
Line 1,609 ⟶ 3,604:
If Not Len(s2$) : PrintN(LSet(s1$,15,Chr(32))+#TAB$+"found nothing.") : EndIf
Next
Input()</
{{out}}
<pre>1001110011 longest sequence: 10011
Line 1,626 ⟶ 3,621:
===Python: Procedural===
<
'check if the first part of the string is repeated throughout the string'
for x in range(len(text)//2, 0, -1):
Line 1,648 ⟶ 3,643:
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'))</
{{out}}
Line 1,665 ⟶ 3,660:
===Python: Functional===
This returns all the possible repeated substrings
<
return [text[:x] for x in range(1, 1 + len(text) // 2)
if text.startswith(text[x:])]
Line 1,694 ⟶ 3,689:
'00' has reps ['0']
'1' has reps []
>>> </
And we could also express this in terms of '''itertools.cycle'''
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''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()</syntaxhighlight>
{{Out}}
<pre>Longest cycles:
'1001110011' -> 10011
'1110111011' -> 1110
'0010010010' -> 001
'1010101010' -> 1010
'1111111111' -> 11111
'0100101101' -> (none)
'0100100' -> 010
'101' -> (none)
'11' -> 1
'00' -> 0
'1' -> (none)</pre>
===Python: Regexp===
This version, inspired by the
<
matchstr = """\
Line 1,722 ⟶ 3,833:
print(re.sub(r'(.+)(\1+)(.*)|(.*)', _checker, txt))
checkit(matchstr)</
{{out}}
Line 1,739 ⟶ 3,850:
===Python: find===
See [https://stackoverflow.com/questions/29481088/how-can-i-tell-if-a-string-repeats-itself-in-python/29489919#29489919 David Zhang's solution] to the same question posed on Stack Overflow.
=={{header|Quackery}}==
<code>factors</code> is defined at [http://rosettacode.org/wiki/Factors_of_an_integer#Quackery Factors of an integer].
<syntaxhighlight lang="quackery"> [ 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 ( $ --> )</syntaxhighlight>
{{out}}
<pre>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".</pre>
=={{header|Racket}}==
<
(define (rep-string str)
Line 1,766 ⟶ 3,919:
"00"
"1")])
(printf "~a => ~a\n" str (or (rep-string str) "not a rep-string")))</
{{Out}}
Line 1,781 ⟶ 3,934:
1 => not a rep-string</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>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)";
}
}</syntaxhighlight>
{{out}}
<pre>10011𝟙𝟘𝟘𝟙𝟙
1110𝟙𝟙𝟙𝟘11
001𝟘𝟘𝟙0010
1010𝟙𝟘𝟙𝟘10
11111𝟙𝟙𝟙𝟙𝟙
0100101101 (no repeat)
010𝟘𝟙𝟘0
101 (no repeat)
1𝟙
0𝟘
1 (no repeat)</pre>
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.
<syntaxhighlight lang="raku" line>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)";
}
}</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="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;
};</syntaxhighlight>
{{out}}
<pre>1001110011 => 10011
1110111011 => 1110
0010010010 => 001
1010101010 => 1010
1111111111 => 11111
0100101101 =>
0100100 => 010
101 =>
11 => 1
00 => 0
1 =></pre>
=={{header|REXX}}==
===version 1===
<
* 11.05.2013 Walter Pachl
* 14.05.2013 Walter Pachl extend to show additional rep-strings
Line 1,834 ⟶ 4,080:
show_norep:
Say right(sq,12) 'is not a repeated string'
Return</
{{Out}}
<pre>'1001110011' has a repetition length of 5 i.e. '10011'
Line 1,855 ⟶ 4,101:
===version 2===
A check was added to validate if the strings are binary strings. The binary strings can be of any length.
<
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
Line 1,870 ⟶ 4,116:
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:
<pre>
Line 1,885 ⟶ 4,131:
1 (no repetitions)
45 ***error*** string isn't a binary string.
</pre>
=={{header|Ring}}==
<syntaxhighlight lang="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
next
</syntaxhighlight>
Output:
<pre>
1001110011 -> 10011
1110111011 -> 1110
0010010010 -> 001
1010101010 -> 1010
1111111111 -> 11111
0100101101 -> 010
0100100 -> 010
101 -> (none)
11 -> 1
00 -> 0
1 -> (none)
</pre>
=={{header|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'''
≫ ≫ '<span style="color:blue">REPSTR</span>' STO
≪ { "1001110011" "1110111011" "0010010010" "1010101010" "1111111111" "0100101101" "0100100" "101" "11" "00" "1" }
{ } 1 3 PICK SIZE '''FOR''' j
OVER j GET <span style="color:blue">REPSTR</span> +
'''NEXT''' SWAP DROP
≫ 'TASK' STO
{{out}}
<pre>
1: { "10011" "1110" "001" "1010" "11111" "" "010" "" "1" "0" "" }
</pre>
=={{header|Ruby}}==
<
1110111011
0010010010
Line 1,903 ⟶ 4,220:
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</
{{Out|Output (as Perl)}}
<pre>1001110011
Line 1,937 ⟶ 4,254:
1
(no repetition)</pre>
=={{header|Rust}}==
<syntaxhighlight lang="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));
}
}
}</syntaxhighlight>
=={{header|Scala}}==
<
def repsOf(s: String) = s.trim match {
case s if s.length < 2 => Nil
Line 1,965 ⟶ 4,365:
val todo = if (args.length > 0) args else tests
todo.map(printReps).foreach(println)
}</
{{out}}
<pre>1001110011: YES (10011)
Line 1,980 ⟶ 4,380:
=={{header|Seed7}}==
<
const func integer: repeatLength (in string: text) is func
Line 2,009 ⟶ 4,409:
end if;
end for;
end func;</
{{out}}
Line 2,025 ⟶ 4,425:
No rep-string for "1"
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="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;</syntaxhighlight>
{{out}}
<pre>1001110011: {'10011'}
1110111011: {'1110'}
0010010010: {'001'}
1010101010: {'10' '1010'}
1111111111: {'1' '11' '111' '1111' '11111'}
0100101101: {}
0100100: {'010'}
101: {}
11: {'1'}
00: {'0'}
1: {}</pre>
=={{header|Sidef}}==
<
0010010010 1010101010
1111111111 0100101101
Line 2,041 ⟶ 4,472:
say "#{n} (no repeat)";
}
}</
{{out}}
<pre>10011𝟙𝟘𝟘𝟙𝟙
Line 2,054 ⟶ 4,485:
0𝟘
1 (no repeat)</pre>
=={{header|Snobol4}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>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
</pre>
=={{header|Swift}}==
<syntaxhighlight lang="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))")
}</syntaxhighlight>
{{out}}
<pre>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: []</pre>
=={{header|Tcl}}==
<
set len [string length $text]
for {set i [expr {$len/2}]} {$i > 0} {incr i -1} {
Line 2,066 ⟶ 4,567:
}
error "no repetition"
}</
Demonstrating:
<
"1001110011" "1110111011" "0010010010" "1010101010" "1111111111"
"0100101101" "0100100" "101" "11" "00" "1"
Line 2,079 ⟶ 4,580:
puts [format "\"%s\" is not a repeated string" $sample]
}
}</
{{out}}
<pre>
Line 2,098 ⟶ 4,599:
{{trans|Tcl}}
{{works with|bash}}
<
local str=$1 len rep part
for (( len = ${#str} / 2; len > 0; len-- )); do
Line 2,132 ⟶ 4,633:
00
1
END_TESTS</
{{out}}
Line 2,148 ⟶ 4,649:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Function rep_string(s)
max_len = Int(Len(s)/2)
Line 2,186 ⟶ 4,687:
WScript.StdOut.WriteLine
Next
</syntaxhighlight>
{{Out}}
Line 2,202 ⟶ 4,703:
1: No Repeating String
</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="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")
}
}
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="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)
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="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
loop</syntaxhighlight>
=={{header|zkl}}==
{{trans|D}}
<
foreach n in ([s.len()/2+1..1,-1]){
Walker.cycle(s[0,n]
if
}
return(False)
}</
{{trans|Python}}
<
foreach n in ([s.len()/2..0,-1]){
if
}
return(False)
}</
<syntaxhighlight lang
foreach w in (words){
if
else [0..*,n].tweak('wrap(z){ if(s:=w[z,n]) s else Void.Stop })
.walk().concat(" ").println();
}</
{{out}}
<pre>
| |||