Power Strings

[Jason Menard]

Borrowed from the Northeastern Illinois University Computer Science Society
Power Strings
=============
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

[B]Sample Input[/B]
abcd
aaaa
ababab
.

[B]Output for Sample Input[/B]
1
4
3

[Joe Pluta]

Not exactly pretty, but I'm tired:

class HighPower {
public static void main(java.lang.String[] args) {
  String[] strings = new String[] { "abcd", "aaaa", "ababab" };
  for (int x = 0; x < strings.length; x++)
  {
    System.out.println("Highpower of " + strings[x] + " = " +
                        highpower(strings[x]));
  }
  System.exit(0);
}
static int highpower(String input)
{
  int high = 1;
  int lenstr = input.length();
  for (int x = 1; x <= lenstr/2; x++) 
  {
    if ((lenstr % x) == 0)
    {
      String ss = input.substring(0,x);
      int power = lenstr/x;
      if (input.equals(repeat(ss, power)))
      {
        high = power;
        break;
      }
    }
  }
  return high;
}
static String repeat(String input, int count)
{
  StringBuffer sb = new StringBuffer();
  while (count-- > 0) sb.append(input);
  return sb.toString();
}
}

[Kao-Wei Wan]

import java.io.*;
class Test
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str=br.readLine())!=null)
        {
            int length=str.length();
            int next_sub=1;
            while(true)
            {
                if(next_sub>(length>>1))
                {
                    next_sub=length;
                    break;
                }
                while(next_sub!=length && str.charAt(0)!=str.charAt(next_sub))
                    next_sub++;
                if(length%next_sub!=0)
                {
                    next_sub++;
                    continue;
                }
                String sub=str.substring(0,next_sub);
                int pos=next_sub;
                while(pos!=length)
                {
                    if(str.indexOf(sub,pos)!=pos)
                        break;
                    pos+=next_sub;
                }
                if(pos==length)
                    break;
                else
                    next_sub++;
            }
            System.out.println(length/next_sub);
        }
    }
}

[ July 20, 2003: Message edited by: Kao-Wei Wan ]

[Jim Yingst]

Here's my solution. Nothing as short and sweet as the above code, but I think my algorithm will be much more efficient for long strings. The basic idea is to find all the prime factors of the input length, and use this info to drastically reduce the number of test which need be performed.
E.g. consider an input of length 30, with factors 2, 3, 5. First test to see if a power of 2 works - is the first half of the string equal to the second? If not, then there will be no point in testing any other multiples of two either. For any even power, the first half of the string would have had to be equal to the second.
Alternately if 2 does work as a power, then to test for additional powers it's sufficient to test just the first half of the string, not the whole string. E.g if the max power was 6, the the power of 2 would have shown up first, and the first 15 chars will also have a power of 3. And once you've found powers of 2 and 3, that means that the initial 30-char string consists of 6 repetitions of a single 5-char string. The only remaining untested factor is 5, and so the only remaining thing to test is if that 5-char substring consists of a single char repeated 5 times. Which will fail if the max power was really 6.
Generally my approach will be a little bit slower than Joe's if the input has very high power, meaning it repeats every 1, 2, 3 chars or so. Becaust those are the first types of patterns Joe tests. But for patterns with longer periods, or patterns with no repetition at all, the factoring method should be a big win, performing far fewer tests.
Primes.java:

import java.util.ArrayList;
import java.util.List;
/** A growable list of all prime numbers up to a given maximum */
public class Primes {
    private static int maxChecked;
    private static List primes = new ArrayList();
    static {
        primes.add(new Integer(2));
        maxChecked = 2;
    }
    /** Get the ith prime number (where 2 is the 0th prime number */
    public static int get(int index) {
        while (primes.size() <= index)
            listUpTo(maxChecked + 10);
        return ((Integer) primes.get(index)).intValue();
    }
    /** Ensure that all primes up to max are listed by this class */
    public static void listUpTo(int max) {
        if (max > maxChecked) {
            for (int num = maxChecked + 1; num <= max; num++)
                check(num);
            maxChecked = max;
        }
    }
    private static void check(int num) {
        for (int i = 0, iMax = primes.size(); i < iMax; i++)
            if (num % get(i) == 0)
                return;
        primes.add(new Integer(num));
    }
    /** For demo/testing */
    public static void main(String[] args) {
        // initial primes
        System.out.println(primes);
        // grow in response to get (sequential)
        for (int i = 0; i < 10; i++)
            get(i);
        System.out.println(primes);
        // grow in response to get (jumping further ahead)
        get(15);
        System.out.println(primes);
        // grow with listUpTo()
        Primes.listUpTo(10000);
        System.out.println(primes);
    }
}

PrimeFactors.java:

import java.util.*;
/**
 * A list of prime factors for a given number.
 * This list never includes 1 or the number itself, even if the number was 
 * prime.  If the input value is prime, the list will be empty.  Conversely if 
 * the list is empty, the input was prime.  This is done so as to guarantee 
 * that while the input value is a long, all prime factors are ints.  If the 
 * input is prime that would be an exception to this rule (it wouldn't fit in 
 * an int) and so this situation must be handled as a special case.
 */
public class PrimeFactors {
    private final long input;
    private long unfactored;
    private ArrayList factors = new ArrayList();
    public PrimeFactors(long input) {
        this.input = input;
        this.unfactored = input;
        findFactors();
    }
    private void findFactors() {
        double maxFactor = Math.sqrt(unfactored);
        for (int i = 0, factor;(factor = Primes.get(i)) <= maxFactor; i++) {
            while (unfactored % factor == 0) {
                factors.add(new Integer(factor));
                unfactored /= factor;
                if (unfactored == 1)
                    return;
                maxFactor = Math.sqrt(unfactored);
            }
        }
        if (unfactored < input)
            factors.add(new Integer((int) unfactored));
    }
    public int size() {
        return factors.size();
    }
    public int get(int i) {
        return ((Integer) factors.get(i)).intValue();
    }
    public List list() {
        return Collections.unmodifiableList(factors);
    }
    public long getInput() {
        return input;
    }
    public boolean isInputPrime() {
        return factors.size() == 0;
    }
    public static void main(String[] args) {
        test(1);
        test(2);
        test(6);
        test(7);
        test(9);
        test(12);
        test(60);
        test(61);
        test(360);
        test(361);
    }
    public static void test(int n) {
        PrimeFactors pf = new PrimeFactors(n);
        System.out.println(n + ":\t" + pf.factors);
    }
}

PowerStrings.java:

import java.io.*;
import java.util.*;
public class PowerStrings {
    private CharSequence sequence;
    private LinkedList factors;
    private PowerStrings(CharSequence input) {
        sequence = input;
        factors = new LinkedList(new PrimeFactors(input.length()).list());
    }
    private int maxPower() {
        int len = sequence.length();
        if (len == 0)
            return 0;
        while (factors.size() > 0) {
            Integer wrapper = (Integer) factors.removeFirst();
            int factor = wrapper.intValue();
            CharSequence sub = tryPower(factor);
            if (sub == null) {
                // factor will not be power of any subsequence either; drop it
                while (factors.remove(wrapper)) {}
            } else {
                // factor is a power - now check subsequence for more factors
                sequence = sub;
                return factor * maxPower();
            }
        }
        if (tryPower(len) != null)
            return len;
        return 1;
    }
    /**
     * Test input to see if it consists of a repeating subsequence with a 
     * specified number of repetitions (the "power").
     * 
     * @param input Sequence to test for repeating subsequence (not null)
     * @param reps Number of times subsequence should repeat
     * @return The repeating subsequence, or null if input has no repetition
     */
    private CharSequence tryPower(int power) {
        final int len = sequence.length();
        assert(len % power == 0);
        CharSequence sub = sequence.subSequence(0, len / power);
        int subLen = sub.length();
        // check to see if remaining input matches repeating subsequence
        for (int x = subLen, y = x + subLen; x < len; x = y, y += subLen)
            if (!sub.equals(sequence.subSequence(x, y)))
                return null; // match failed - quit
        // tests passed - input is repeating substring
        return sub;
    }
    /** 
     * Read lines from standard input and report the power of each line 
     * until terminated with "." 
     */
    public static void main(String[] args) throws IOException {
        Primes.listUpTo(100);
        process(new InputStreamReader(System.in));
    }
    /** 
     * Read lines and report the power of each line until terminated with "." 
     */
    public static void process(Reader in) throws IOException {
        BufferedReader reader = new BufferedReader(in);
        for (String line;((line = reader.readLine()) != null)  :wink:   {
            line = line.trim();
            if (line.equals("."))
                return;
            System.out.println(maxPowerOf(line));
        }
    }
    /**
     * Find the maximum "power" of a CharSequence.  
     * @param input Sequence to check for repetitions (not null)
     * @return The "power" - the number of repetitions for the smallest 
     * repeating subsequence in input.  If input is blank, power is 0.
     */
    public static int maxPowerOf(CharSequence input) {
        return new PowerStrings(input).maxPower();
    }
}

And some JUnit tests which came in handy:
PowerStrings.java:

import junit.framework.TestCase;
public class PowerStringsTest extends TestCase {
    public void testInputs() {
        //doTest("", 0);
        doTest("a", 1);
        doTest("aa", 2);
        doTest("aaa", 3);
        doTest("aaaa", 4);
        doTest("ab", 1);
        doTest("aba", 1);
        doTest("abab", 2);
        doTest("aaaaaaaaaaaa", 12);
        doTest("abababababab", 6);
        doTest("abcabcabcabc", 4);
        doTest("abcdabcdabcd", 3);
        doTest("abcdefabcdef", 2);
        doTest("abcdefghijkl", 1);
        doTest(1, 1);
        doTest(1, 100);
        doTest(100, 1);
    }
    /**
     * Test with a given input and expected power
     */
    public void doTest(String input, int expectedPower) {
        assertEquals(expectedPower, PowerStrings.maxPowerOf(input));
    }
    /**
     * Test using a generated sample string with a given sequence length and power
     */
    public void doTest(int sequenceLen, int power) {
        String input = makeSampleString(sequenceLen, power);
        assertEquals(power, PowerStrings.maxPowerOf(input));
    }
    private String makeSampleString(int sequenceLen, int power) {
        StringBuffer sb = new StringBuffer(sequenceLen);
        for (char ch = '0', max = (char) (ch + sequenceLen); ch < max; ch++)
            sb.append(ch);
        String sequence = sb.toString();
        sb = new StringBuffer(sequenceLen * power);
        for (int i = 0; i < power; i++)
            sb.append(sequence);
        return sb.toString();
    }
    /** 
     * Test all possible powers for input length 360 
     * (chosen for its many repeated factors)
     */
    public void test360() {
        doReciprocalTests(360, 1);
        doReciprocalTests(360, 2);
        doReciprocalTests(360, 3);
        doReciprocalTests(360, 4);
        doReciprocalTests(360, 5);
        doReciprocalTests(360, 6);
        doReciprocalTests(360, 8);
        doReciprocalTests(360, 9);
        doReciprocalTests(360, 10);
        doReciprocalTests(360, 12);
        doReciprocalTests(360, 15);
        doReciprocalTests(360, 18);
    }
    private void doReciprocalTests(int len, int power) {
        assert(len % power == 0);
        doTest(360 / power, power);
        doTest(power, 360 / power);
    }
    public void testPerformance() {
        doTimedTest(4617445, 1);
        doTimedTest(253, 493);
        doTimedTest(9883, 23);
        doTimedTest(23, 9883);
        doTimedTest(7457, 645);
        doTimedTest(4253, 3253);
    }
    public void doTimedTest(int sequenceLen, int power) {
        String input = makeSampleString(sequenceLen, power);
        long before = System.currentTimeMillis();
        int p = PowerStrings.maxPowerOf(input);
        long after = System.currentTimeMillis();
        assertEquals(power, p);
        System.out.println(
            "Time for length "
                + (sequenceLen * power)
                + "\tpower "
                + power
                + ":\t"
                + (after - before));
    }
}

[ July 21, 2003: Message edited by: Jim Yingst ]

[Jim Yingst]

Heh. Well, after doing it my way I finally took a closer look at KWW's code, and see now that there's a reasonably simple algorithm I missed. Ah well. I already had the Primes and PrimeFactors code - the additional code I wrote here is roughly equivalent in complexity to KWW's code, but when you include the two preexisting classes as well, mine's a lot more complex. In terms of performance they're very comparable (both kicking Joe's code's butt) Ah well, live and learn...

[Kao-Wei Wan]

Thanks,Jim Yingst
Now I add a liitle code to the original to make it more efficient
This will use the searching result to help us to find the sub-string more quickly...
Don't waste any useful information

                int pos=next_sub;
                int plus=0;
                while(pos!=length)
                {
                    if((plus=str.indexOf(sub,pos))!=pos)
                        break;
                    pos+=next_sub;
                }
                if(pos==length)
                    break;
                else
                {
                    if(plus==-1)
                    {
                        next_sub=length;
                        break;
                    }
                    next_sub=plus;
                }

[ July 21, 2003: Message edited by: Kao-Wei Wan ]

[Jim Yingst]

Well, this is fun. I decided to look more at performance of these two programs (KWW's and mine) in various circumstances. I created a wider variety of tests:

import junit.framework.TestCase;
import java.util.Random;
public class PowerStringsTest extends TestCase {
    public void testInputs() {
        //doTest("", 0);
        doTest("a", 1);
        doTest("aa", 2);
        doTest("aaa", 3);
        doTest("aaaa", 4);
        doTest("ab", 1);
        doTest("aba", 1);
        doTest("abab", 2);
        doTest("aaaaaaaaaaaa", 12);
        doTest("abababababab", 6);
        doTest("abcabcabcabc", 4);
        doTest("abcdabcdabcd", 3);
        doTest("abcdefabcdef", 2);
        doTest("abcdefghijkl", 1);
        doTimedTest(1, 1);
        doTimedTest(1, 100);
        doTimedTest(100, 1);
    }
    /**
     * Test with a given input and expected power
     */
    public void doTest(String input, int expectedPower) {
        int power = PowerStrings.maxPowerOf(input);
        assertEquals(expectedPower, power);
    }
    private String makeSampleString(int sequenceLen, int power) {
        Random rand = new Random(1);
        StringBuffer sb = new StringBuffer(sequenceLen);
        for (int i = 0; i < sequenceLen; i++) {
            char ch = (char) ('a' + rand.nextInt(26));
            sb.append(ch);
        }
        String sequence = sb.toString();
        sb = new StringBuffer(sequenceLen * power);
        for (int i = 0; i < power; i++)
            sb.append(sequence);
        return sb.toString();
    }
    /** 
     * Test all possible powers for input length 360 
     * (chosen for its many repeated factors)
     */
    public void test360() {
        doReciprocalTests(360, 1);
        doReciprocalTests(360, 2);
        doReciprocalTests(360, 3);
        doReciprocalTests(360, 4);
        doReciprocalTests(360, 5);
        doReciprocalTests(360, 6);
        doReciprocalTests(360, 8);
        doReciprocalTests(360, 9);
        doReciprocalTests(360, 10);
        doReciprocalTests(360, 12);
        doReciprocalTests(360, 15);
        doReciprocalTests(360, 18);
    }
    private void doReciprocalTests(int len, int power) {
        assert(len % power == 0);
        doTimedTest(360 / power, power);
        doTimedTest(power, 360 / power);
    }
    public void testPerformance() {
        doTimedTest(4617445, 1);
        doTimedTest(6347448, 1);
        doTimedTest(4617445, 2);
        doTimedTest(6347448, 2);
        doTimedTest(1, 4617445);
        doTimedTest(1, 6347448);
        doTimedTest(253, 493);
        doTimedTest(9883, 23);
        doTimedTest(23, 9883);
        doTimedTest(7457, 645);
        doTimedTest(4253, 3253);
        doTimedTest(makeSampleString(1, 2355) + "X", 1);
        doTimedTest(makeSampleString(1, 8246666) + "X", 1);
        doTimedTest(makeSampleString(1, 12524321) + "X", 1);
        doTimedTest("X" + makeSampleString(1, 2355), 1);
        doTimedTest("X" + makeSampleString(1, 8246666), 1);
        doTimedTest("X" + makeSampleString(1, 12524321), 1);
    }
    public void doTimedTest(int sequenceLen, int power) {
        String input = makeSampleString(sequenceLen, power);
        doTimedTest(input, power);
    }
    private void doTimedTest(String input, int expectedPower) {
        long before = System.currentTimeMillis();
        int p = PowerStrings.maxPowerOf(input);
        long after = System.currentTimeMillis();
        assertEquals(expectedPower, p);
        System.out.println(
            "input length = "
                + (input.length())
                + "\tpower = "
                + expectedPower
                + "\ttime = "
                + (after - before));
    }
}

I revised the makeSampleString() method to use lower-case alpha chars only, in a (pseudo-)random order. Though the random seed is set to 1 always, for reproducibility. This didn't have a big effect on stats. I also created a number of additional tests for very long strings with either very high or very low powers. These produced the most extreme variations in performance between the two programs
Here are the times for the last 17 tests for each program. (All the earlier tests were too short to measure really - all 0-10 milliseconds.

     Input       Power       Time (ms)
     length
                             KWW         Jim
1    4617445     1           190         10
2    6347448     1           241         0
3    234890      2           380         270
4    12694896    2           571         301
5    4617445     4617445     842         301
6    6347448     6347448     1172        340
7    124729      493         0           10
8    227309      23          10          10
9    227309      9883        10          10
10   4809765     645         190         251
11   13835009    3253        560         661
12   2356        1           0           0
13   8246667     1           1513        4837
14   12524322    1           2303        6630
15   2356        1           0           0
16   8246667     1           621         0
17   12524322    1           991         0

The last six were interesting - I created some very unusual strings. For rows 12-14 I created very long strings that were all the same character, except the very last char is different. E.g. oooooooooooX, but much longer. (So it looks like a very high-power string until the end, but it's actually power 1.) Then for rows 15-17 I put the odd char in front rather than at the end - Xooooooooooo. I was expecting KWW to perform poorer on 12-14, and better on 15-17 - was surprised to see the reverse. I'm still not sure why that is. It's very annoying - without rows 12-14 I think I could claim a clear victory. Oh well...
Incidentally, I did use KWW's revised code, but it didn't seem to make any significant difference.

[Jim Yingst]

Of course for brevity, there's also

import java.util.regex.*;
public class RegexPowerStrings {
    private static final Pattern pattern = Pattern.compile("\\A(.+?)\\1*\\Z");
    public static int maxPowerOf(CharSequence input) {
        Matcher m = pattern.matcher(input);
        m.find();
        return input.length() / m.group(1).length();
    }
}

Unfortunately the performance for this, well, sucks. Especially once it gets to line 13 from the previous table - I skipped 13 and 14 because they tookway too long. Here's the revised table:

     Input       Power       Time (ms)
     length
                             KWW         Jim         Regex
 1   4617445     1           190         10          2764        
 2   6347448     1           241         0           3715        
 3   9234890     2           380         270         3726        
 4   12694896    2           571         301         5097        
 5   4617445     4617445     842         301         1382        
 6   6347448     6347448     1172        340         2263        
 7   124729      493         0           10          20          
 8   227309      23          10          10          40          
 9   227309      9883        10          10          40          
10   4809765     645         190         251         671         
11   13835009    3253        560         661         2964        
12   2356        1           0           0           240         
13   8246667     1           1513        4837        XXXX            
14   12524322    1           2303        6630        XXXX            
15   2356        1           0           0           0           
16   8246667     1           621         0           6529        
17   12524322    1           991         0           7561        

[Joe Pluta]

(frumph!)
Hey, I'm an application developer, not a CompSci major . I didn't see anything about performance as part of the question! My job is to get the code to work.
Besides, my version kicks BUTT on one-character strings .
Anyway, good job, guys. You not only showed me some great code, but made my head hurt at the same time!
Joe

[Jim Yingst]

Hey, I'm an application developer, not a CompSci major . I didn't see anything about performance as part of the question! My job is to get the code to work.
Absolutely. And being first to market is a big plus, congratulations. But it also means that those who come later need to work harder to differentiate themselves somehow. Kicking your butt in performance seemed like a good way to do that.
Besides, my version kicks BUTT on one-character strings .

Anyway, good job, guys. You not only showed me some great code, but made my head hurt at the same time!
In fact this was the true objective.
I am curious if any regex whizzes out there (you know who you are) see any good alternative to the regex solution I posted. Seems like there are often a bunch of different ways to approach a problem with a regex; so far I'm only seeing one, so I figure I'm probably missing something. Of course we could replace //A and //Z with ^ and $; no big deal there. Is there any significant variation possible?

[Kao-Wei Wan]

Jim Yingst, you are nice to test the performance
for us.
Thank you
Can you do me a favor to test the performance of the code below,please? Thank you very much
I want to know if this will be better or not
Thank you

import java.io.*;
class Test
{
public static void main(String args[]) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str;
while((str=br.readLine())!=null)
{
int sub=1;
char seq[]=str.toCharArray();
int length=seq.length;
int i;
for(i=1;i<length;++i)
if(seq[i]!=seq[0])
break;
if(i==seq.length)
{
System.out.println(1);
continue;
}
                        seq=null;
sub=i+1;
while(true)
{
if(sub>(length>>1))
{
sub=length;
break;
}
String substr=str.substring(0,sub);
int pos=sub;
int plus=0;
while(pos<length && (plus=str.indexOf(substr,pos))==pos)
pos+=sub;
if(pos==length)
break;
else
{
if(plus==-1)
{
sub=length;
break;
}
sub=plus;
}
}
System.out.println(length/sub);
}
}
}

[ July 23, 2003: Message edited by: Kao-Wei Wan ]
[ July 23, 2003: Message edited by: Kao-Wei Wan ]