CODEWITHSUNDEEP
algorithm
pkvprakash
pkvprakash

Reputation: 329

Periodic Binary Strings

Is there any efficient algorithms to check whether a binary string is periodic or not?

Let S be a binary string and H be the set of sub strings of S. Then S is said to be periodic if it can be obtained by concatenating one or more times, at least one h in H, also h != S .

Upvotes: 9

Views: 7841

Answers (5)

Todd Davies
Todd Davies

Reputation: 5522

Here is an implementation of a O(m + (n-1)) algorithm (where m is the input length, and n is the cycle length).

Based of the Knuth Morris Pratt algorithm, it iterates over the input string, checking to see if the substring input[0:i] is a repeated pattern. If it finds a character in the input string that isn't in the pattern, then i is updated to become the index of that character. This means characters in the string are not compared more than once.

public static String findSequence(String input) {
  out: for (int i = 0; i < input.length();) {
    for (int j = i; j < input.length(); j++) {
      if(input.charAt(j % (i+1)) != input.charAt(j)) {
        i = j;
        continue out;
      }
    }
    return (String) input.subSequence(0, i + 1);
  }
  return ""; // Impossible
}

Upvotes: 0

MBo
MBo

Reputation: 80287

Initial string S with length Len. Double the string (really we need S + half of S). Search for occurrence of initial string S in doubled string SS, beginning from 2nd position, ending at Len/2 + 1. If such occurence exists with position P, then S is periodic with period P - 1.

S = abbaabbaabba Len = 12 SS = abbaabbaabbaabbaabbaabba

Searching from 2nd to 7th position, S found at P=5, period = 4

S = abaabaabaabb SS = abaabaabaabbabaabaabaabb

S doesn't occur in SS (except for 1 and L+1), no period exists

P.S. Note due to useful Venkatesh comment: We need to add minimal possible periodic unit, it's length is L/2 for even-size strings, and maximum divisor of L for odd-size strings (if length is prime number, string cannot be periodic). Simple factorization methods have O(N^1/2) complexity, more complex - O(N^1/4), so sometimes it is worth to factorize length to avoid unnecessary comparison of long strings.

Upvotes: 9

abhineet
abhineet

Reputation: 225

private static boolean isPeriodic(String string) {
int stringLength = string.length();
if (stringLength <= 1) {
    return false;
}
boolean flag = true;

for (int i = 1; i <= stringLength / 2; i++) {
if (string.length() % i == 0) {
if (flag && i > 1) {
    return flag;
}
flag = true;
for (int j = i; j < stringLength;) {

if ((j + i) <= stringLength) {

if (string.substring(0, i).equals(
        string.substring(j, j + i))) {
    j = j + i;
    continue;
} else {
    flag = false;
    break;

}
} else {
    break;
}

}
}

}
return flag;
}

Upvotes: 1

Petar Ivanov
Petar Ivanov

Reputation: 93060

First of all for this to happen it's necessary that length(h) divides length(S).

If k = length(S)/length(h), then for a given k it's easy to check whether the string is periodic.

Indeed, it's periodic if the number represented by S is divisible by 100..0100..0...100..0. That's the number which is of length length(S), has k blocks of equal length and each block has only the highest bit set.

Upvotes: 1

Ofir
Ofir

Reputation: 8372

I'm pretty sure it is possible to improve on this, but I would have started by breaking the length of S (I'll call that L) to prime factors, and checking for a period of length of S/f for each prime factor f (len(h) must divide len(S) and I'm since not looking for the shortest possible h, prime L/len(h) is enough).

As to improvements, random check order would help in some circumstances (to prevent constructing input for worse case scenarios, etc.).

Upvotes: 3

Related Questions