计算给定长度string可能的最大运行次数

几个星期前，Lembik 问了下面的问题：

一个stringw周期p是任何正整数p ，使得无论何时定义该方程的两边， w[i]=w[i+p] 。 令per(w)表示per(w)的最小周期的大小。 我们说一个stringw是周期性的if per(w) <= |w|/2 。

所以非正式的一个周期性的string就是一个由另一个string组成的string，它至less被重复一次。 唯一的麻烦是，在string的末尾，我们不需要重复string的完整副本，只要它至less重复一次。

例如，考虑stringx = abcab 。 per(abcab) = 3因为x[1] = x[1+3] = a ， x[2]=x[2+3] = b并且没有更小的周期。 stringabcab因此不是周期性的。 然而，stringababa是周期性的per(ababa) = 2 。

更多的例子， abcabca ， ababababa和abcabcabc也是周期性的。

对于那些喜欢正则expression式的人来说，这个检测string是否是周期性的：

 \b(\w*)(\w+\1)\2+\b 

其任务是在一个更长的string中查找所有最大的周期性子string。 这些在文献中有时被称为运行 。

w[i,j]的子串w[i,j]是周期性的最大周期子串（run）， w[i-1] = w[i-1+p]也不w[j+1] = w[j+1-p] 。 非正式地说，“跑”不能包含在同一时期的一个更大的“跑”中。

由于两次运行可以表示在整个string中不同位置出现的相同string，我们将按间隔表示运行。 上面的定义是按照区间重复的。

一个stringT中的运行（或最大周期性子string）是一个区间[i...j]其中j>=i ，

• T[i...j]是周期为p = per(T[i...j])的周期性单词
• 这是最大的。 forms上，既没有T[i-1] = T[i-1+p]也没有T[j+1] = T[j+1-p] 。 在非正式的情况下，运行不能在同一个时期进行较大的运行。

由RUNS(T)表示stringT的一组运行。

运行的例子

• 在T = atattatt的四个最大周期子串（运行）是T[4,5] = tt ， T[7,8] = tt ， T[1,4] = atat ， T[2,8] = tattatt 。

• stringT = aabaabaaaacaacac包含以下7个最大周期子串（运行）： T[1,2] = aa ， T[4,5] = aa ， T[7,10] = aaaa ， T[12,13] = aa ， T[13,16] = acac ， T[1,8] = aabaabaa ， T[9,15] = aacaaca 。

• stringT = atatbatatb包含以下三个运行。 它们是： T[1, 4] = atat ， T[6, 9] = atat和T[1, 10] = atatbatatb 。

在这里，我正在使用1索引。

目标

编写代码，使得对于从2开始的每个整数n，输出包含在长度为n任何二进制string中的最大数量的运行。

示例optima

在下面： n, optimum number of runs, example string 。

 2 1 00 3 1 000 4 2 0011 5 2 00011 6 3 001001 7 4 0010011 8 5 00110011 9 5 000110011 10 6 0010011001 11 7 00100110011 12 8 001001100100 13 8 0001001100100 14 10 00100110010011 15 10 000100110010011 16 11 0010011001001100 17 12 00100101101001011 18 13 001001100100110011 19 14 0010011001001100100 

有没有更快的方法来find增加值n的最佳运行次数比一个天真的O（n ^ 2 2 ^ n）时间方法？

Answer 1

代数algorithmfind所有的解决scheme

理念

在每一个string中，最后一个字符只能用于有限的运行。

最后一个0只能添加一个运行

 10 + 0 => 100 

自从

 00 + 0 => 000 

这只是一个重复。 如果它添加了最小运行，下一个可能的最小运行添加是

 110010 + 0 => 1100100 

再次注意

 010010 + 0 => 0100100 

不是一个额外的运行，这是一个重复。 下一个可能的增加是

 111001001100100 1111001001100100111001001100100 ... 

数字可以变化，但最小的长度是

 3, 7, 15, 31 

这是

 4^1 - 1, 4^2 - 1, ..., 4^n - 1 

因此，在string开始处，不需要不同的字符

 maxaddlast = 4^n - 2 

通过添加最后一个字符产生可以添加的最大运行次数。

algorithm

• 在search长度为n时，所有variables都以[maxNumberOfRuns – maxaddlast（n + 1），maxNumberOfRuns]中的运行计数logging。
• 要find一个解决schememaxNumberOfRuns n + 1只是所有logging的变体扩展0和1，并检查。

种子

剩下的问题是大小堆栈收集未来种子所需的所有变种。

由于没有足够的数据来猜测有效的公式，因此select自适应algorithm：

1. n的初始堆栈大小被猜测从n – 1
2. 对于每个解决scheme，检查使用的堆栈大小，堆栈中总是有1的空间。
3. 如果堆栈在某个n处被完全使用，堆栈大小将增加，并且在n处重新开始计算。

结果

 length 104 with 91 runs 

在600秒内达到。 然后内存用完了默认设置。 使用-Xmx16G或更多。 对于较大的数字，必须修改代码以将种子保留在磁盘上，而不是保存在内存中。

而且比暴力方法快得多。

** 代码 **

这里是我在Java中的示例代码：

 import java.io.BufferedReader; import java.io.FileReader; import java.io.FileWriter; import java.util.ArrayList; import de.bb.util.Pair; /** * A search algorithm to find all runs for increasing lengths of strings of 0s * and 1s. * * This algorithm uses a seed to generate the candidates for the next search. * The seed contains the solutions for rho(n), rho(n) - 1, ..., minstart(n). * Since the seed size is unknown, it starts with a minimal seed: minstart(n) = * rho(n) - 1; After the solutions are calculated the all seeds are checked. If * a seed with minstart(n) was used, that minstart(n) gets decremented and the * search is restarted at position n + 1. This guarantees that the seed is * always large enough. * * Optional TODO: Since the seed can occupy large amounts of memory, the seed is * maintained on disk. * * @author Stefan "Bebbo" Franke (c) 2016 */ public class MaxNumberOfRunsAdaptive { private static long start; private ArrayList<Pair<byte[], ArrayList<Integer>>> seed = new ArrayList<>(); private int max; private ArrayList<ArrayList<Pair<byte[], ArrayList<Integer>>>> nextSeedStack; private ArrayList<Integer> maxs = new ArrayList<>(); private ArrayList<Integer> diffs = new ArrayList<>(); private ArrayList<Integer> totals = new ArrayList<>(); private int total; private byte[] buffer; public static void main(String[] args) { int limit = 9999; if (args.length == 1) { try { limit = Integer.parseInt(args[0]); } catch (Exception e) { } } start = System.currentTimeMillis(); new MaxNumberOfRunsAdaptive().run(limit); long took = (System.currentTimeMillis() - start) / 100; System.out.println("took " + (took / 10.) + "s"); } /** * Find a string with the max number of runs for all lengths from 2 to * limit; * * @param limit * the limit to stop calculation. */ private void run(int limit) { maxs.add(0); maxs.add(0); diffs.add(0); diffs.add(1); totals.add(0); totals.add(0); ArrayList<Integer> n0 = new ArrayList<Integer>(); n0.add(0); seed.add(Pair.makePair(new byte[] { '0' }, n0)); saveSeed(2); for (int i = 2; i <= limit;) { int restart = compose(i); if (restart < i) { System.out.println("*** restarting at: " + restart + " ***"); i = restart; loadSeed(i); total = totals.get(i - 1); } else { saveSeed(i + 1); ++i; } } } /** * Load the seed for the length from disk. * * @param length */ private void loadSeed(int length) { try { seed.clear(); final FileReader fr = new FileReader("seed-" + length + ".txt"); final BufferedReader br = new BufferedReader(fr); for (String line = br.readLine(); line != null; line = br.readLine()) { final int space = line.indexOf(' '); final byte[] b = line.substring(0, space).getBytes(); final String sends = line.substring(space + 2, line.length() - 1); final ArrayList<Integer> ends = new ArrayList<>(); for (final String s : sends.split(",")) { ends.add(Integer.parseInt(s.trim())); } seed.add(Pair.makePair(b, ends)); } fr.close(); } catch (Exception e) { throw new RuntimeException(e); } } /** * Save the seed for the given length to the disk. * * @param length * the length */ private void saveSeed(int length) { try { final FileWriter fos = new FileWriter("seed-" + length + ".txt"); for (final Pair<byte[], ArrayList<Integer>> p : seed) { fos.write(new String(p.getFirst()) + " " + p.getSecond().toString() + "\n"); } fos.close(); } catch (Exception e) { throw new RuntimeException(e); } } /** * Compose new strings from all available bases. Also collect the candidates * for the next base. */ private int compose(int length) { max = 0; int nextStackSize; if (diffs.size() > length) nextStackSize = diffs.get(length) + 1; else nextStackSize = diffs.get(length - 1) - 1; if (nextStackSize < 2) nextStackSize = 2; // setup collector for next bases nextSeedStack = new ArrayList<>(); for (int i = 0; i < nextStackSize; ++i) { nextSeedStack.add(new ArrayList<Pair<byte[], ArrayList<Integer>>>()); } buffer = new byte[length]; // extend the bases for (Pair<byte[], ArrayList<Integer>> e : seed) { final byte[] s = e.getFirst(); System.arraycopy(s, 0, buffer, 0, length - 1); if (s.length < 3 || s[s.length - 1] == '1' || s[s.length - 2] == '1' || s[s.length - 3] == '1') { buffer[length - 1] = '0'; test(length, e.getSecond()); } if (s.length < 3 || s[s.length - 1] == '0' || s[s.length - 2] == '0' || s[s.length - 3] == '0') { buffer[length - 1] = '1'; test(length, e.getSecond()); } } long took = (System.currentTimeMillis() - start) / 100; final ArrayList<String> solutions = new ArrayList<String>(); for (Pair<byte[], ArrayList<Integer>> p : nextSeedStack.get(nextSeedStack.size() - 1)) { solutions.add(new String(p.getFirst())); } total += solutions.size(); if (totals.size() <= length) totals.add(0); totals.set(length, total); if (maxs.size() <= length) { maxs.add(0); } maxs.set(length, max); System.out.println(length + " " + max + " " + (took / 10.) + " " + total + " " + solutions); seed.clear(); // setup base for next level for (ArrayList<Pair<byte[], ArrayList<Integer>>> t : nextSeedStack) { seed.addAll(t); } if (diffs.size() <= length) { diffs.add(1); } int restart = length; // check for restart for (final String b : solutions) { for (int i = 2; i < b.length(); ++i) { int diff = maxs.get(i) - countRuns(b.substring(0, i)); if (diff >= diffs.get(i)) { if (i < restart) restart = i; diffs.set(i, diff + 1); } } } System.out.println(diffs); return restart; } /** * Test the current buffer and at it to the next seed stack, * * @param l * the current length * @param endRuns * the end runs to store */ void test(final int l, final ArrayList<Integer> endRuns) { final ArrayList<Integer> r = incrementalCountRuns(l, endRuns); final int n = r.get(r.size() - 1); // shift the nextBaseStack while (max < n) { nextSeedStack.remove(0); nextSeedStack.add(new ArrayList<Pair<byte[], ArrayList<Integer>>>()); ++max; } // add to set in stack, if in stack final int index = nextSeedStack.size() - 1 - max + n; if (index >= 0) nextSeedStack.get(index).add(Pair.makePair(buffer.clone(), r)); } /** * Find incremental the runs incremental. * * @param l * the lengths * @param endRuns * the runs of length-1 ending at length -1 * @return a new array containing the end runs plus the length */ private ArrayList<Integer> incrementalCountRuns(final int l, final ArrayList<Integer> endRuns) { final ArrayList<Integer> res = new ArrayList<Integer>(); int sz = endRuns.size(); // last end run dummy - contains the run count int n = endRuns.get(--sz); int pos = 0; for (int i = l - 2; i >= 0; i -= 2) { int p = (l - i) / 2; // found something ? if (equals(buffer, i, buffer, i + p, p)) { while (i > 0 && buffer[i - 1] == buffer[i - 1 + p]) { --i; } int lasti = -1; while (pos < sz) { lasti = endRuns.get(pos); if (lasti <= i) break; lasti = -1; ++pos; } if (lasti != i) ++n; res.add(i); } } res.add(n); return res; } /** * Compares one segment of a byte array with a segment of a 2nd byte array. * * @param a * first byte array * @param aOff * offset into first byte array * @param b * second byte array * @param bOff * offset into second byte array * @param len * length of the compared segments * @return true if the segments are equal, otherwise false */ public final static boolean equals(byte a[], int aOff, byte b[], int bOff, int len) { if (a == null || b == null) return a == b; while (len-- > 0) if (a[aOff + len] != b[bOff + len]) return false; return true; } /** * Simple slow stupid method to count the runs in a String. * * @param s * the string * @return the count of runs. */ static int countRuns(String s) { int n = 0; int l = s.length(); for (int i = 0; i < l - 1; ++i) { for (int k = i + 1; k < l; ++k) { int p = 0; while (i + p < k && k + p < l) { if (s.charAt(i + p) != s.charAt(k + p)) break; ++p; } if (i + p == k) { int jj = k + p - 1; if (i > 0 && s.charAt(i - 1) == s.charAt(i - 1 + p)) { continue; } while (jj + 1 < l && s.charAt(jj + 1) == s.charAt(jj + 1 - p)) { ++jj; ++k; } ++n; } } } return n; } } 

Answer 2

部分答案。 这个想法是从Boyer-Moorestringsearchalgorithm中取出一个页面，适当修改，以便匹配的string来自源string。

考虑一个长度为n的string寻找周期为k运行的问题，其中2k < n 。 如果这个问题有一个多项式时间algorithm，那么就有一个问题。 只要对每个2 <= k <= n/2运行一次这样的algorithm。 如果特定的问题以O(p(n))运行，其中p具有度d ，则一般问题将以d+1的多项式运行。 因此，检查具体问题就足够了。

让inputstring为T[0 ... n-1] 。 这里的关键是要认识到，如果T[i] != T[i+k] ，那么索引对(i, i+k)就会阻碍运行的存在。 当我们看到一个障碍物时，我们可以把这个问题细分成两个问题： T[0 ... i+k-1]和T[i+1 ... n-1] 。 如果这些string中的任何一个太短，那么algorithm什么都不会发出并终止; 当运行不存在时，这是recursion终止的方式。 现在查找障碍物i+1 ， i+2 ，…，直到i+k-1 。 如果有的话，劈开。 另一方面，如果没有障碍物的序列[i ... i+k-1] ，那么我们有一个长度为2k的游程。 如果我们find一个运行，我们发现我们最大限度地扩展它（这很容易），然后将问题分成三部分：前缀，运行和后缀。 我们发出跑步，现在我们有两个问题，前缀和后缀，每个短。 为了recursion运行，select一个初始值为(n+k)/2 i 。

这是部分答案的原因是我遗漏了这是一个多项式时间algorithm的分析。 certificate不是微不足道的原因是，当你有障碍时，长度i+k和ni-1加起来大于n n+k-1 ，所以可以想象，总input长度在recursion栈上可能成倍增长。 需要进一步的论证来certificate这实际上并没有发生。