CODEWITHSUNDEEP
stringalgorithm
Shivam Mitra
Shivam Mitra

Reputation: 1052

Representation of string as some power of substring

Given a string, we have to check if a string can be represented by a substring of it repeated some finite times.

ababab -> (ab)^3

I saw a solution which says to first find the longest proper prefix which is also a suffix. Let the length of this prefix be some k. Let n be the length of the original string. If n%(n-k) == 0, the string can be represented as a substring repeated finite times. Otherwise,no.

I am not able to understand the logic behind this solution. Can anybody explain me why this solution works? Link where I saw this solution:geeksforgeeks

Upvotes: 2

Views: 283

Answers (2)

AnotherGeek
AnotherGeek

Reputation: 884

If n%(n-k) == 0, the string can be represented as a substring repeated finite times. Otherwise,no. This statement is very helpful in the algorithm so let's start by proving it
If n-k is length of the suffix so if n%(n-k) != 0 n will be equal to the concatination of q string with length = n-k and a string with length minor to n-k (q = n / (n-k))
So n in this case can't be the square of the suffix
Reasoning by opposition lead
Now let's write the code

 class Program
    {
        static void Main(string[] args)
        {
            string myString = "abab";
            int k = suffixLentgth(myString);
            if (k > 0)
            {
                Console.WriteLine(myString.Substring(k, myString.Length - k));
            }

        }
        static int suffixLentgth(string ch)
        {
            int n = ch.Length;
            for (int i = 2; i < n; i++)
            {
                bool isPower = true;
                if (n % (n - i) == 0) // this suffix can fulfil your dreams
                {
                    for (int j = 0; j < (n / (n - i)) - 1; j++)
                    {
                        if (ch.Substring((n - i) * j, n - i) != ch.Substring((n - i) * (j + 1), n - i))
                        {
                            isPower = false;
                            break;
                        }
                    }
                    if (isPower)
                        return i;
                }
            }
            return 0;
        }

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

Ok, so first, let call the substring that forms input string A. So, 

input = A ^ a (with a is constant)

We can see that, the longest proper prefix which is also a suffix should cover at least half of the input if input is a power string. The prove is simple

  • If a is even, the case is trivial.

  • If a is odd, so input = (A^b)A(A^b), we can see that, the longest prefix suffix should be at least (A^b)A (with b = (a - 1)/2)

So, now, let consider three cases:

  • If the length k of the prefix suffix is k < n/2 , so n - k > n/2 -> n % (n - k) != 0, as proved above, this string cannot be a power string.

  • If the length k of the prefix suffix is k = n/2 -> this case is trivial.

  • If the length k of the prefix suffix is k > n/2, so, we can visualize the input string as

    input = ACA

    With C is the overlapping area between the prefix and suffix, and as prefix and suffix are equaled, we can see that

    AC = CA

    Let assume length of C > A, in order for AC = CA, so , we can divide C into C = A + B -> A + A + B = A + B + A, this can only happen if A == B.

    So, the input will have the form input = AAAA which is clearly a power string. In case C = A, we have input = AAA, and case C < A can be proved similar to case C > A.

Upvotes: 3

Related Questions