How to resolve the algorithm Rep-string step by step in the Forth programming language

Published on 12 May 2024 09:40 PM
#Forth

How to resolve the algorithm Rep-string step by step in the Forth programming language

Table of Contents

Problem Statement

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Rep-string step by step in the Forth programming language

Source code in the forth programming language

: 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 ;


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

You may also check:How to resolve the algorithm Wordiff step by step in the J programming language
You may also check:How to resolve the algorithm Pentagram step by step in the C programming language
You may also check:How to resolve the algorithm Greatest subsequential sum step by step in the Lua programming language
You may also check:How to resolve the algorithm Lucas-Lehmer test step by step in the Factor programming language
You may also check:How to resolve the algorithm Substring step by step in the jq programming language