logo标签列表

计算给定长度字符串的最大运行次数

stringalgorithmmath
42
几周前，Lembik提出了以下问题：（链接） 引用如下：
字符串w的周期p是任何正整数p，满足当此等式两边都有定义时，w[i]=w[i+p]。让per(w)表示w的最小周期大小。如果per(w)<=|w|/2，则称字符串w为周期性的。
因此，周期性字符串通俗地说就是由另一个字符串重复至少一次构成的字符串。唯一的复杂之处在于，在字符串的末尾，我们不需要完整复制重复的字符串，只要它至少被完整地重复一次即可。
例如，考虑字符串x=abcab。per(abcab)=3，因为x[1]=x[1+3]=a，x[2]=x[2+3]=b，且没有更小的周期。因此，字符串abcab不是周期性的。然而，字符串ababa是周期性的，因为per(ababa)=2。
其他周期性字符串的例子还包括abcabca、ababababa和abcabcabc。
对于那些喜欢正则表达式的人，以下正则表达式可以检测一个字符串是否是周期性的：
\b(\w*)(\w+\1)\2+\b

任务是在一个较长的字符串中找到所有最大周期子串。在文献中，它们有时被称为 runs 。

字符串 w 的子串 w [i，j] 是最大周期子串（run），如果它是周期性的，且既不满足 w [i-1] = w [i-1 + p] 也不满足 w [j +1] = w [j +1-p]。简单来说，“run”不能包含在具有相同周期的较大的“ run ”中。

因为两个runs可以代表出现在整个字符串中不同位置上的相同字符序列，所以我们将以区间表示runs。下面是以上定义的区间版本。

字符串T中的运行（或最大周期子串）是一个区间[i... j] ，其中j≥i，使得

  • T [i ... j] 是周期词，并且其周期为p = per(T [i ... j])
  • 它是最大的，形式上，既不满足 T [i-1] = T [i-1 + p] 也不满足T [j +1] = T [j +1-p]。简单来说，“run”不能包含在具有相同周期的较大的“ run ”中。

用RUNS（T）表示字符串T中的所有runs。

runs 的示例

  • 字符串T = atattatt 中的四个最大周期子串（runs）分别是 T [4,5] = tt ，T [7,8] = tt，T [1,4] = atat 和 T [2,8] = tattatt。

  • 字符串T = aabaabaaaacaacac 包含以下7个最大周期子串（runs）：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。

  • 字符串T = atatbatatb 包含以下三个runs： T [1, 4] = atat ，T [6, 9] = atat 和 T [1, 10] = atatbatatb 。

这里使用1索引。

目标

编写代码，使得对于每个从2开始的整数n，您都可以输出任何长度为n的二进制字符串中包含的最大运行次数。

最佳答案示例

以下是：n，最优运行次数，示例字符串。

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

有没有比朴素的O(n^2 2^n)时间复杂度更快地找到增加n值的最优运行次数的方法？
我的替代方法正在形成，但它产生了一些不同的结果--例如，在上面的最佳结果中，您有“12 7 001001010010”，但我的代码输出“12 8 110110011011”，其中周期1运行为（11、11、00、11、11），周期3运行为（110110、011011）并且有一个周期4运行（01100110）--我在计算运行时错了吗？ - cdlane
Lembik的问题现在已经添加了修正值。 - Simd
@AdamSilenko 这个问题是“编写代码，使得对于每个从2开始的整数n，您输出任何长度为n的二进制字符串中包含的最大运行次数。” - Simd
这个长度为10的解决方案怎么样：0011001100 - 具有5个1序列 (00, 11, 00, 11, 00) 和2个2序列 (00110011, 11001100) -> 7个序列？ - bebbo
“5 2 00011”似乎是错误的，因为只有T [4,5] = 11是有效的。 T [1,2] = 00被拒绝，因为T [j + 1] = T [j + 1-p]，而T [2,3] = 00被拒绝，因为T [i-1] = T [i-1 + p]。 - bebbo
显示剩余6条评论
2个回答
2

一种寻找所有解决方案的分代算法

思想

在每个字符串中，最后一个字符只能对有限数量的连续组成部分产生贡献。

末尾的0只能增加一行：

10 + 0 => 100

自从在

00 + 0 => 000

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

110010 + 0 => 1100100

再次注意

010010 + 0 => 0100100

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

111001001100100
1111001001100100111001001100100
...

数字可能会有所不同，但最小长度为
3, 7, 15, 31

which is

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

在字符串开头，不需要使用不同的字符，因此：
maxaddlast = 4^n - 2

通过添加最后一个字符，获得可以添加的最大运行次数。

算法

  • 在查找长度为 n 的过程中，所有变量都记录了在 [maxNumberOfRuns - maxaddlast(n+1), maxNumberOfRuns] 范围内的运行计数。
  • 要找到 n+1 的最大运行次数解决方案，只需将所有记录的变量扩展为 0 和 1 并进行检查即可。

种子

剩余的问题是调整堆栈大小以收集所有未来种子所需的变量。

由于没有足够的数据来猜测一个有效的公式，选择自适应算法:

  1. n 的初始堆栈大小从 n - 1 中猜测。
  2. 对于每个解决方案，检查使用的堆栈大小，确保堆栈始终有一个空间。
  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;
    }
}
确实，长度为n的所有解，其运行计数在[maxNumberOfRuns(n) - maxaddlast(n + 1), maxNumberOfRuns(n)]范围内，足以找到运行计数为maxNumberOfRuns(n)的所有长度为n + 1的解。但是它们是否足以找到运行计数在[maxNumberOfRuns(n + 1) - naxaddlast(n + 2), maxNumberOfRuns(n + 1)]范围内的所有长度为n + 1的解（这样您就可以找到长度为n + 2的最优解等）？ - Anders Kaseorg
startsWith("0010")这个优化绝对是错误的：按照你的代码输出是 8 4 0.0 00100100，缺少长度为8，并且有5次运行的字符串 00110011。即使移除了该优化，它仍然给出一个长度为205的185次运行的字符串，缺少长度为205，并且有186次运行的字符串 0110101101001011010110100110101101001011010110100101101001101011010010110101101001101011010010110101101001011010110100110101101001011010110100101101001101011010010110101101001101011010010110101101001011010。 - Anders Kaseorg
@AndersKaseorg：我会查看这些种子。但是你的例子与文本不匹配。你给出的字符串长度为177和221，而不是165和205。/耸肩 - bebbo
问题要求一个算法，而不是猜测，上面我已经证明你的猜测是错误的：它导致你输出长度为8的4连续字符串，而不是长度为5的5连续字符串，还有长度为165的147连续字符串，而不是长度为148的148连续字符串。 - Anders Kaseorg
让我们在聊天中继续这个讨论。 - bebbo
显示剩余5条评论
0

部分答案。思路是借鉴 Boyer-Moore 字符串搜索算法的一部分，适当修改以匹配源字符串中的字符串。

考虑长度为 n 的字符串寻找周期为 k 的运行问题，其中 2k < n。如果有一个多项式时间算法解决这个问题，那么就可以为一般问题提供一个算法。只需为每个 2 <= k <= n/2 运行一次这样的算法。如果特定问题的运行时间为 O(p(n))，其中 p 的次数为 d，则一般问题将使用次数为 d+1 的多项式运行。因此，检查特定问题就足够了。

假设输入字符串为T[0 ... n-1]。关键在于意识到如果T[i] != T[i+k]，那么索引对(i, i+k)会阻碍运行的存在。当我们遇到障碍时，我们可以将问题分成两个更短的输入字符串问题：T[0 ... i+k-1]和T[i+1 ... n-1]。如果这些字符串中有任何一个太短，则算法不发出任何内容并终止；这是递归在运行不存在时终止的方式。现在寻找障碍物i+1，i+2，...，直到i+k-1。如果存在任何障碍物，则进行切割。另一方面，如果存在一个序列[i ... i+k-1]没有障碍物，则我们有一个长度为2k的运行。如果我们找到了一个运行，我们就会最大限度地扩展它（这很容易），然后将问题分成三个部分：前缀、运行和后缀。我们发出运行，并且现在有两个问题，前缀和后缀，每个都更短。要递归运行此操作，请选择一个初始值为(n+k)/2的i。

这是一个部分答案的原因是我忽略了这是一个多项式时间算法的分析。证明不是微不足道的原因是，当你有一个障碍时，长度和加起来等于，这比大，所以可以想象递归堆栈上的总输入长度可能会呈指数增长。需要进一步的论证来表明这实际上并没有发生。
两点。首先，关于您最后一段关于递归堆栈增长的问题，这是不可能的。请注意，当您将字符串拆分为“left+obstruction”和“obstruction+right”时，您不能进一步以这样的方式拆分字符串，即仍然将“obstruction”视为一个整体。在下一步中，必须使用或删除“obstruction”，因为它距子字符串的末尾不到“k”的距离。 - Kittsil
其次，这不是一个部分解决方案，因为它根本不是解决方案！您已经展示了一种新的多项式时间方法来检查给定字符串中的运行情况。而不是所有长度为n的二进制字符串。可以想象，您可以反转此过程以构建最佳字符串，但当前呈现的方式并非如此。您所做的只是展示了一种在原始O(n^2 2^n)中获得O(n^2)的新方法。 - Kittsil
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接