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

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Rep-string step by step in the ALGOL 68 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 ALGOL 68 programming language

Source code in the algol programming language

# 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                                    #
main:
(

    []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
)

  

You may also check:How to resolve the algorithm Documentation step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the Smalltalk programming language
You may also check:How to resolve the algorithm Cheryl's birthday step by step in the Scala programming language
You may also check:How to resolve the algorithm Number names step by step in the Objective-C programming language
You may also check:How to resolve the algorithm Collections step by step in the NetRexx programming language