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

Published on 12 May 2024 09:40 PM
#D

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

Source code in the d programming language

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));
    }
}

You may also check:How to resolve the algorithm Empty string step by step in the Dyalect programming language
You may also check:How to resolve the algorithm Linear congruential generator step by step in the uBasic/4tH programming language
You may also check:How to resolve the algorithm Loops/Infinite step by step in the Ol programming language
You may also check:How to resolve the algorithm Terminal control/Cursor movement step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Archimedean spiral step by step in the Kotlin programming language