Repeated Substring Pattern

🏠 ⬅️ ➡️

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

Input: s = "abab " Output: true Explanation: It is the substring "ab " twice.

Example 2:

Input: s = "aba " Output: false

Example 3:

Input: s = "abcabcabcabc " Output: true Explanation: It is the substring "abc " four times or the substring "abcabc " twice.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
⚠️ Correct 
program main
    implicit none

    character(len=100) :: s
    logical :: result

    ! Example 1
    s = "abab "
    result = solve(s)
    print '(L1)', result

    ! Example 2
    s = "aba "
    result = solve(s)
    print '(L1)', result

    ! Example 3
    s = "abcabcabcabc "
    result = solve(s)
    print '(L1)', result

contains

    function solve(s) result(result)
        implicit none
        character(len=*), intent(in) :: s
        integer :: i, j, k
        logical :: result

        do i = 1, len_trim(s) - 1
            do j = i + 1, len_trim(s)
                do k = 1, (j-i+1)/(j-i)
                    if (s(i:j) == s(i:(j-k*(j-i)))) then
                        result = .true.
                        return
                    end if
                end do
            end do
        end do
        result = .false.
    end function solve
end program main
✅ Compiled
❌ Executed
❌ Correct 
program solve_the_problem
      implicit none

      character(len=1000) :: s
      integer :: i, j, k
      logical :: found

      read(*,*) s

      ! Check if the string can be constructed by taking a substring of it and appending multiple copies of the substring together
      do i = 1, len(s) - 1
          do j = i + 1, len(s)
              if (s(i:j) == s(i:j)) then
                  found = .true.
                  do k = 1, len(s) / (j - i + 1)
                      if (s(i:j) /= s(i:j)) then
                          found = .false.
                          exit
                      end if
                  end do
                  if (found) then
                      write(*,*) "true"
                      stop
                  end if
              end if
          end do
      end do

      write(*,*) "false"

      end program solve_the_problem
🌐 Data from online sources 
def can_construct(s):
    n = len(s)
    for i in range(n // 2, 0, -1):
        if n % i == 0:
            substr = s[:i]
            flag = True
            for j in range(i, n, i):
                if s[j:j+i] != substr:
                    flag = False
                    break

            if flag:
                return True

    return False

The algorithm iterates through possible substring lengths from half of the length of the given string down to 1 (inclusive). For each length `i`, it checks if the given string can be divided into substrings of equal length `i`. If yes, it takes the first substring and checks if all the remaining substrings of the same length are equal to the first one.

If all the substrings are equal, the function returns true, meaning the given string can be constructed by appending multiple copies of the substring together. If none of the lengths results in equal substrings, the function returns false.

🌐 Data from online sources 
bool can_construct(string s) {
    int n = s.size();
    for (int i = n / 2; i > 0; --i) {
        if (n % i == 0) {
            string substr = s.substr(0, i);
            bool flag = true;
            for (int j = i; j < n; j += i) {
                if (s.substr(j, i) != substr) {
                    flag = false;
                    break;
                }
            }

            if (flag) return true;
        }
    }
    return false;
}

The algorithm iterates through possible substring lengths from half of the length of the given string down to 1 (inclusive). For each length `i`, it checks if the given string can be divided into substrings of equal length `i`. If yes, it takes the first substring and checks if all the remaining substrings of the same length are equal to the first one.

If all the substrings are equal, the function returns true, meaning the given string can be constructed by appending multiple copies of the substring together. If none of the lengths results in equal substrings, the function returns false.