string计数 - title
计算给定长度字符串可能的最大运行次数 (2)
几周前,Lembik 提出以下问题:
字符串
w
周期p
是任何正整数p
,使得每当定义该等式的两侧时w[i]=w[i+p]
。 设per(w)
表示per(w)
的最小周期的大小。 我们说字符串w
是周期性iffper(w) <= |w|/2
。
所以非正式地,周期性字符串只是一个字符串,由至少重复一次的另一个字符串组成。 唯一的复杂因素是,在字符串的末尾,我们不需要重复字符串的完整副本,只要它至少重复一次即可。
例如,考虑字符串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
任务是在较长的字符串中查找所有最大周期性子字符串。 这些有时被称为文献中的运行 。
w[i,j]
的子串w[i,j]
是最大周期子串(run),如果它是周期性的并且w[i-1] = w[i-1+p]
也不是w[j+1] = w[j+1-p]
。 非正式地,“运行”不能包含在具有相同周期的较大“运行”中。
因为两个运行可以表示在整个字符串中的不同位置出现的相同字符串,所以我们将按间隔表示运行。 以下是以间隔重复的上述定义。
字符串
T
中的run(或最大周期子字符串)是j>=i
的区间[i...j]
,这样
T[i...j]
是周期词,周期为p = per(T[i...j])
- 它是最大的。 形式上,
T[i-1] = T[i-1+p]
和T[j+1] = T[j+1-p]
。 非正式地,运行不能包含在具有相同周期的较大运行中。
由RUNS(T)
表示字符串T
的运行集。
运行的例子
串
T = atattatt
中的四个最大周期子串(运行)是T[4,5] = tt
,T[7,8] = tt
,T[1,4] = atat
,T[2,8] = tattatt
。字符串
T = 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
。字符串
T = atatbatatb
包含以下三个运行。 它们是:T[1, 4] = atat
,T[6, 9] = atat
T[1, 4] = atat
,T[6, 9] = atat
T[1, 10] = atatbatatb
。
我在这里使用1索引。
目标
编写代码,以便对于从2开始的每个整数n,输出包含在长度为n
任何二进制字符串中的最大运行n
。
示例最佳
在以下内容中: 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
是否有更快的方法来找到增加
n
值的最佳运行次数而不是天真的O(n ^ 2 2 ^ n)时间方法?
寻找所有解决方案的世代算法
想法
在每个字符串中,最后一个字符只能用于有限数量的运行。
最后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
在字符串开始时,不需要不同的字符
maxaddlast = 4^n - 2
产生可以通过添加最后一个字符添加的最大运行次数。
算法
- 在完成对长度n的搜索时,所有变量都以[maxNumberOfRuns - maxaddlast(n + 1),maxNumberOfRuns]中的运行计数记录。
- 要找到maxNumberOfRuns为n + 1的解决方案,只需将所有记录的变量扩展为0和1并进行检查。
种子
剩下的问题是调整堆栈大小以收集未来种子所需的所有变体。
由于没有足够的数据来猜测有效公式,因此选择了自适应算法:
- n的初始堆栈大小从n - 1开始猜测
- 对于每个解决方案,检查使用的堆栈大小,堆栈中始终有1个空间。
- 如果堆栈在某些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;
}
}
部分答案。 我们的想法是从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]
。 如果这些字符串中的任何一个太短,则算法不会发出任何内容并终止; 这是当运行不存在时递归终止的方式。 现在寻找障碍物a i+1
, i+2
,......,直到i+k-1
。 如果存在,切割。 另一方面,如果有一个没有障碍物的序列[i ... i+k-1]
,那么我们有一个长度为2k
的跑道。 如果我们找到一个运行,我们发现我们最大限度地扩展它(这很容易),然后将问题分成三部分:前缀,运行和后缀。 我们发出了运行,现在我们有两个问题,前缀和后缀,每个都更短。 要以递归方式运行此选项,请选择值为(n+k)/2
的初始i
。
这是部分答案的原因是我忽略了这是一个多项式时间算法的分析。 证明不是微不足道的原因是,当你有障碍时,长度i+k
和ni-1
加起来n+k-1
,大于n
,所以可以想象总输入长度在递归堆栈上可能会呈指数级增长。 需要进一步论证,以证明这实际上并未发生。