查找表达式在字符串中连续和非连续出现的次数
Finding the Number of Times an Expression Occurs in a String Continuously and Non Continuously
我在 phone 上进行了编码面试，并被问到这个问题：
Given a String (for example):
"aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc"
和一个表达式（例如）：
"a+b+c-"
其中：
+: means the char before it is repeated 2 times
-: means the char before it is repeated 4 times
求给定表达式在字符串中出现的操作数非连续和连续出现的次数。
以上表达式出现4次：
1) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
2) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
3) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
4) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
我不知道该怎么做。我开始使用带有大量索引标记的迭代蛮力方法，但意识到在中途编写代码会有多么混乱和困难：
import java.util.*;
public class Main {
public static int count(String expression, String input) {
int count = 0;
ArrayList<char[]> list = new ArrayList<char[]>();
// Create an ArrayList of chars to iterate through the expression and match to string
for(int i = 1; i<expression.length(); i=i+2) {
StringBuilder exp = new StringBuilder();
char curr = expression.charAt(i-1);
if(expression.charAt(i) == '+') {
exp.append(curr).append(curr);
list.add(exp.toString().toCharArray());
}
else { // character is '-'
exp.append(curr).append(curr).append(curr).append(curr);
list.add(exp.toString().toCharArray());
}
}
char[] inputArray = input.toCharArray();
int i = 0; // outside pointer
int j = 0; // inside pointer
while(i <= inputArray.length) {
while(j <= inputArray.length) {
for(int k = 0; k< list.size(); k++) {
/* loop through
* all possible combinations in array list
* with multiple loops
*/
}
j++;
}
i++;
j=i;
}
return count;
}
public static void main(String[] args) {
String expression = "a+b+c-";
String input = "aaksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
System.out.println("The expression occurs: "+count(expression, input)+" times");
}
}
在花了很多时间反复地做之后，他提到了递归，我仍然看不出递归的明确方法，我无法解决这个问题。我现在正在尝试解决它 post-interview 但我仍然不确定如何解决这个问题。我应该如何解决这个问题？解决方案是否显而易见？我认为这对于编码 phone 面试来说是一个非常难的问题。
递归可能如下（伪代码）：
int search(String s, String expression) {
if expression consists of only one token t /* e. g. "a+" */ {
search for t in s
return number of occurrences
} else {
int result = 0
divide expression into first token t and rest expression
// e. g. "a+a+b-" -> t = "a+", rest = "a+b-"
search for t in s
for each occurrence {
s1 = substring of s from the position of occurrence to the end
result += search(s1, rest) // search for rest of expression in rest of string
}
return result
}
}
将此应用于整个字符串，您将获得非连续出现的次数。要获得连续出现，您根本不需要递归——只需将表达式转换为字符串并通过迭代搜索。
如何预处理 aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc？
这变成a1k1s1d1b1a2l1a1s1k1d1h1f1b2l1a1j1d1f1h1a1c4a1o1u1d1g1a1l1s1a2b2l1i1s1d1f1h1c4
现在查找出现的 a2、b2、c4。
尝试了下面的代码，但现在它只给出了基于深度优先的第一个可能的匹配。
需要进行更改以进行所有可能的组合，而不是首先进行
import java.util.ArrayList;
import java.util.List;
public class Parsing {
public static void main(String[] args) {
String input = "aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
System.out.println(input);
for (int i = 0; i < input.length(); i++) {
System.out.print(i/10);
}
System.out.println();
for (int i = 0; i < input.length(); i++) {
System.out.print(i%10);
}
System.out.println();
List<String> tokenisedSearch = parseExp("a+b+c-");
System.out.println(tokenisedSearch);
parse(input, 0, tokenisedSearch, 0);
}
public static boolean parse(String input, int searchFromIndex, List<String> tokensToSeach, int currentTokenIndex) {
if(currentTokenIndex >= tokensToSeach.size())
return true;
String token = tokensToSeach.get(currentTokenIndex);
int found = input.indexOf(token, searchFromIndex);
if(found >= 0) {
System.out.println("Found at Index "+found+ " Token " +token);
return parse(input, searchFromIndex+1, tokensToSeach, currentTokenIndex+1);
}
return false;
}
public static List<String> parseExp(String exp) {
List<String> list = new ArrayList<String>();
String runningToken = "";
for (int i = 0; i < exp.length(); i++) {
char at = exp.charAt(i);
switch (at) {
case '+' :
runningToken += runningToken;
list.add(runningToken);
runningToken = "";
break;
case '-' :
runningToken += runningToken;
runningToken += runningToken;
list.add(runningToken);
runningToken = "";
break;
default :
runningToken += at;
}
}
return list;
}
}
我们称字符串的长度为n，查询表达式的长度（根据"units"的个数，如a+或b-）m.
不清楚你所说的"continuously"和"non-continuously"是什么意思，但是如果"continuously"意味着查询字符串单元之间不能有任何间隙，那么你可以使用 KMP algorithm 在 O(m+n) 时间内找到所有实例。
我们可以在 O(nm) 时间内求解 "non-continuous" 版本，用 dynamic programming 求解 space。基本上，我们要计算的是一个函数：
f(i, j) = the number of occurrences of the subquery consisting of the first i units
of the query expression, in the first j characters of the string.
因此对于您的示例，f(2, 41) = 2，因为在您的示例字符串的前 41 个字符中有 2 个单独出现的子模式 a+b+。
最终答案将是 f(n, m)。
我们可以递归计算如下：
f(0, j) = 0
f(i, 0) = 0
f(i > 0, j > 0) = f(i, j-1) + isMatch(i, j) * f(i-1, j-len(i))
其中 len(i) 是表达式中第 i 个单元的长度（始终为 2 或 4），isMatch(i, j) 是一个函数 returns 1 如果表达式中的第 i 个单元匹配位置 j 处的文本 ending，否则为 0。例如，在您的示例中 isMatch(15, 2) = 1，因为 s[14..15] = bb。这个函数只需要常数时间 运行，因为它永远不需要检查超过 4 个字符。
上面的递归已经按原样工作了，但是我们可以通过确保只解决每个子问题一次来节省时间。因为函数 f() 只依赖于它的 2 个参数 i 和 j，它们的范围分别在 0 和 m 之间，以及 0 和 n 之间，我们可以计算所有 n*m 可能的答案并将它们存储在 table.
[编辑：正如 Sasha Salauyou 指出的那样，space 要求实际上可以减少到 O(m)。我们永远不需要访问 k < j-1 的 f(i, k) 的值，所以不用在 table 中存储 m 列，我们可以只存储 2，并通过始终访问列 [=19] 在它们之间交替=].]
想亲自尝试一下，并认为我也可以分享我的解决方案。当表达式中确实存在 char 0 时，parse 方法显然存在问题（尽管这本身可能是更大的问题），find 方法将因空 [=15] 而失败=] 数组，我不确定 ab+c- 是否应该被视为有效模式（我这样对待它）。请注意，这仅涵盖到目前为止的非连续部分。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Matcher {
public static void main(String[] args) {
String haystack = "aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
String[] needles = parse("a+b+c-");
System.out.println("Needles: " + Arrays.toString(needles));
System.out.println("Found: " + find(haystack, needles, 0));
needles = parse("ab+c-");
System.out.println("Needles: " + Arrays.toString(needles));
System.out.println("Found: " + find(haystack, needles, 0));
}
private static int find(String haystack, String[] needles, int i) {
String currentNeedle = needles[i];
int pos = haystack.indexOf(currentNeedle);
if (pos < 0) {
// Abort: Current needle not found
return 0;
}
// Current needle found (also means that pos + currentNeedle.length() will always
// be <= haystack.length()
String remainingHaystack = haystack.substring(pos + currentNeedle.length());
// Last needle?
if (i == needles.length - 1) {
// +1: We found one match for all needles
// Try to find more matches of current needle in remaining haystack
return 1 + find(remainingHaystack, needles, i);
}
// Try to find more matches of current needle in remaining haystack
// Try to find next needle in remaining haystack
return find(remainingHaystack, needles, i) + find(remainingHaystack, needles, i + 1);
}
private static String[] parse(String expression) {
List<String> searchTokens = new ArrayList<String>();
char lastChar = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
char[] chars;
switch (c) {
case '+':
// last char is repeated 2 times
chars = new char[2];
Arrays.fill(chars, lastChar);
searchTokens.add(String.valueOf(chars));
lastChar = 0;
break;
case '-':
// last char is repeated 4 times
chars = new char[4];
Arrays.fill(chars, lastChar);
searchTokens.add(String.valueOf(chars));
lastChar = 0;
break;
default:
if (lastChar != 0) {
searchTokens.add(String.valueOf(lastChar));
}
lastChar = c;
}
}
return searchTokens.toArray(new String[searchTokens.size()]);
}
}
输出：
Needles: [aa, bb, cccc]
Found: 4
Needles: [a, bb, cccc]
Found: 18
非递归算法，需要 O(m) space 并在 O(n*m) 中运行，其中 m 是查询中的标记数：
@Test
public void subequences() {
String input = "aabbccaacccccbbd";
String query = "a+b+";
// here to store tokens of a query: e.g. {a, +}, {b, +}
char[][] q = new char[query.length() / 2][];
// here to store counts of subsequences ending by j-th token found so far
int[] c = new int[query.length() / 2]; // main
int[] cc = new int[query.length() / 2]; // aux
// tokenize
for (int i = 0; i < query.length(); i += 2)
q[i / 2] = new char[] {query.charAt(i), query.charAt(i + 1)};
// init
char[] sub2 = {0, 0}; // accumulator capturing last 2 chars
char[] sub4 = {0, 0, 0, 0}; // accumulator capturing last 4 chars
// main loop
for (int i = 0; i < input.length(); i++) {
shift(sub2, input.charAt(i));
shift(sub4, input.charAt(i));
boolean all2 = sub2[1] != 0 && sub2[0] == sub2[1]; // true if all sub2 chars are same
boolean all4 = sub4[3] != 0 && sub4[0] == sub4[1] // true if all sub4 chars are same
&& sub4[0] == sub4[2] && sub4[0] == sub4[3];
// iterate tokens
for (int j = 0; j < c.length; j++) {
if (all2 && q[j][1] == '+' && q[j][0] == sub2[0]) // found match for "+" token
cc[j] = j == 0 // filling up aux array
? c[j] + 1 // first token, increment counter by 1
: c[j] + c[j - 1]; // add value of preceding token counter
if (all4 && q[j][1] == '-' && q[j][0] == sub4[0]) // found match for "-" token
cc[j] = j == 0
? c[j] + 1
: c[j] + c[j - 1];
}
if (all2) sub2[1] = 0; // clear, to make "aa" occur in "aaaa" 2, not 3 times
if (all4) sub4[3] = 0;
copy(cc, c); // copy aux array to main
}
}
System.out.println(c[c.length - 1]);
}
// shifts array 1 char left and puts c at the end
void shift(char[] cc, char c) {
for (int i = 1; i < cc.length; i++)
cc[i - 1] = cc[i];
cc[cc.length - 1] = c;
}
// copies array contents
void copy(int[] from, int[] to) {
for (int i = 0; i < from.length; i++)
to[i] = from[i];
}
主要思想是从输入中一个一个地捕获字符，将它们保存在 2 字符和 4 字符的累加器中，并检查它们是否与查询的某些标记匹配，记住我们得到了多少匹配项到目前为止以这些标记结尾的子查询。
查询 (a+b+c-) 被拆分为标记 (a+、b+、c-)。然后我们在累加器中收集字符并检查它们是否匹配某些标记。如果我们找到第一个标记的匹配项，我们将其计数器加 1。如果我们找到另一个 j-th 标记 的匹配项，我们可以创建与 子查询匹配的其他子序列由标记 [0...j] 组成，因为现在存在许多标记 对于由标记 [0...j-1] 组成的子查询，因为此匹配可以附加到它们中的每一个。
例如，我们有：
a+ : 3 (3 matches for a+)
b+ : 2 (2 matches for a+b+)
c- : 1 (1 match for a+b+c-)
cccc 到达时。然后 c- 计数器应该增加 b+ 计数器值，因为到目前为止我们有 2 个 a+b+ 子序列并且 cccc 可以附加到它们。
如果您首先使用简单的 parser/compiler 转换搜索字符串，因此 a+ 变为 aa 等，那么您可以简单地使用此字符串和 运行 一个正则表达式与你的干草堆相匹配。 （抱歉，我不是 Java 程序员，所以无法提供任何真正的代码，但这并不难）
我在 phone 上进行了编码面试，并被问到这个问题：
Given a String (for example):
"aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc"
和一个表达式（例如）：
"a+b+c-"
其中：
+: means the char before it is repeated 2 times
-: means the char before it is repeated 4 times
求给定表达式在字符串中出现的操作数非连续和连续出现的次数。
以上表达式出现4次：
1) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
2) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
3) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
4) aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc
^^ ^^ ^^^^
aa bb cccc
我不知道该怎么做。我开始使用带有大量索引标记的迭代蛮力方法，但意识到在中途编写代码会有多么混乱和困难：
import java.util.*;
public class Main {
public static int count(String expression, String input) {
int count = 0;
ArrayList<char[]> list = new ArrayList<char[]>();
// Create an ArrayList of chars to iterate through the expression and match to string
for(int i = 1; i<expression.length(); i=i+2) {
StringBuilder exp = new StringBuilder();
char curr = expression.charAt(i-1);
if(expression.charAt(i) == '+') {
exp.append(curr).append(curr);
list.add(exp.toString().toCharArray());
}
else { // character is '-'
exp.append(curr).append(curr).append(curr).append(curr);
list.add(exp.toString().toCharArray());
}
}
char[] inputArray = input.toCharArray();
int i = 0; // outside pointer
int j = 0; // inside pointer
while(i <= inputArray.length) {
while(j <= inputArray.length) {
for(int k = 0; k< list.size(); k++) {
/* loop through
* all possible combinations in array list
* with multiple loops
*/
}
j++;
}
i++;
j=i;
}
return count;
}
public static void main(String[] args) {
String expression = "a+b+c-";
String input = "aaksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
System.out.println("The expression occurs: "+count(expression, input)+" times");
}
}
在花了很多时间反复地做之后，他提到了递归，我仍然看不出递归的明确方法，我无法解决这个问题。我现在正在尝试解决它 post-interview 但我仍然不确定如何解决这个问题。我应该如何解决这个问题？解决方案是否显而易见？我认为这对于编码 phone 面试来说是一个非常难的问题。
递归可能如下（伪代码）：
int search(String s, String expression) {
if expression consists of only one token t /* e. g. "a+" */ {
search for t in s
return number of occurrences
} else {
int result = 0
divide expression into first token t and rest expression
// e. g. "a+a+b-" -> t = "a+", rest = "a+b-"
search for t in s
for each occurrence {
s1 = substring of s from the position of occurrence to the end
result += search(s1, rest) // search for rest of expression in rest of string
}
return result
}
}
将此应用于整个字符串，您将获得非连续出现的次数。要获得连续出现，您根本不需要递归——只需将表达式转换为字符串并通过迭代搜索。
如何预处理 aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc？
这变成a1k1s1d1b1a2l1a1s1k1d1h1f1b2l1a1j1d1f1h1a1c4a1o1u1d1g1a1l1s1a2b2l1i1s1d1f1h1c4
现在查找出现的 a2、b2、c4。
尝试了下面的代码，但现在它只给出了基于深度优先的第一个可能的匹配。
需要进行更改以进行所有可能的组合，而不是首先进行
import java.util.ArrayList;
import java.util.List;
public class Parsing {
public static void main(String[] args) {
String input = "aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
System.out.println(input);
for (int i = 0; i < input.length(); i++) {
System.out.print(i/10);
}
System.out.println();
for (int i = 0; i < input.length(); i++) {
System.out.print(i%10);
}
System.out.println();
List<String> tokenisedSearch = parseExp("a+b+c-");
System.out.println(tokenisedSearch);
parse(input, 0, tokenisedSearch, 0);
}
public static boolean parse(String input, int searchFromIndex, List<String> tokensToSeach, int currentTokenIndex) {
if(currentTokenIndex >= tokensToSeach.size())
return true;
String token = tokensToSeach.get(currentTokenIndex);
int found = input.indexOf(token, searchFromIndex);
if(found >= 0) {
System.out.println("Found at Index "+found+ " Token " +token);
return parse(input, searchFromIndex+1, tokensToSeach, currentTokenIndex+1);
}
return false;
}
public static List<String> parseExp(String exp) {
List<String> list = new ArrayList<String>();
String runningToken = "";
for (int i = 0; i < exp.length(); i++) {
char at = exp.charAt(i);
switch (at) {
case '+' :
runningToken += runningToken;
list.add(runningToken);
runningToken = "";
break;
case '-' :
runningToken += runningToken;
runningToken += runningToken;
list.add(runningToken);
runningToken = "";
break;
default :
runningToken += at;
}
}
return list;
}
}
我们称字符串的长度为n，查询表达式的长度（根据"units"的个数，如a+或b-）m.
不清楚你所说的"continuously"和"non-continuously"是什么意思，但是如果"continuously"意味着查询字符串单元之间不能有任何间隙，那么你可以使用 KMP algorithm 在 O(m+n) 时间内找到所有实例。
我们可以在 O(nm) 时间内求解 "non-continuous" 版本，用 dynamic programming 求解 space。基本上，我们要计算的是一个函数：
f(i, j) = the number of occurrences of the subquery consisting of the first i units
of the query expression, in the first j characters of the string.
因此对于您的示例，f(2, 41) = 2，因为在您的示例字符串的前 41 个字符中有 2 个单独出现的子模式 a+b+。
最终答案将是 f(n, m)。
我们可以递归计算如下：
f(0, j) = 0
f(i, 0) = 0
f(i > 0, j > 0) = f(i, j-1) + isMatch(i, j) * f(i-1, j-len(i))
其中 len(i) 是表达式中第 i 个单元的长度（始终为 2 或 4），isMatch(i, j) 是一个函数 returns 1 如果表达式中的第 i 个单元匹配位置 j 处的文本 ending，否则为 0。例如，在您的示例中 isMatch(15, 2) = 1，因为 s[14..15] = bb。这个函数只需要常数时间 运行，因为它永远不需要检查超过 4 个字符。
上面的递归已经按原样工作了，但是我们可以通过确保只解决每个子问题一次来节省时间。因为函数 f() 只依赖于它的 2 个参数 i 和 j，它们的范围分别在 0 和 m 之间，以及 0 和 n 之间，我们可以计算所有 n*m 可能的答案并将它们存储在 table.
[编辑：正如 Sasha Salauyou 指出的那样，space 要求实际上可以减少到 O(m)。我们永远不需要访问 k < j-1 的 f(i, k) 的值，所以不用在 table 中存储 m 列，我们可以只存储 2，并通过始终访问列 [=19] 在它们之间交替=].]
想亲自尝试一下，并认为我也可以分享我的解决方案。当表达式中确实存在 char 0 时，parse 方法显然存在问题（尽管这本身可能是更大的问题），find 方法将因空 [=15] 而失败=] 数组，我不确定 ab+c- 是否应该被视为有效模式（我这样对待它）。请注意，这仅涵盖到目前为止的非连续部分。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Matcher {
public static void main(String[] args) {
String haystack = "aksdbaalaskdhfbblajdfhacccc aoudgalsaa bblisdfhcccc";
String[] needles = parse("a+b+c-");
System.out.println("Needles: " + Arrays.toString(needles));
System.out.println("Found: " + find(haystack, needles, 0));
needles = parse("ab+c-");
System.out.println("Needles: " + Arrays.toString(needles));
System.out.println("Found: " + find(haystack, needles, 0));
}
private static int find(String haystack, String[] needles, int i) {
String currentNeedle = needles[i];
int pos = haystack.indexOf(currentNeedle);
if (pos < 0) {
// Abort: Current needle not found
return 0;
}
// Current needle found (also means that pos + currentNeedle.length() will always
// be <= haystack.length()
String remainingHaystack = haystack.substring(pos + currentNeedle.length());
// Last needle?
if (i == needles.length - 1) {
// +1: We found one match for all needles
// Try to find more matches of current needle in remaining haystack
return 1 + find(remainingHaystack, needles, i);
}
// Try to find more matches of current needle in remaining haystack
// Try to find next needle in remaining haystack
return find(remainingHaystack, needles, i) + find(remainingHaystack, needles, i + 1);
}
private static String[] parse(String expression) {
List<String> searchTokens = new ArrayList<String>();
char lastChar = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
char[] chars;
switch (c) {
case '+':
// last char is repeated 2 times
chars = new char[2];
Arrays.fill(chars, lastChar);
searchTokens.add(String.valueOf(chars));
lastChar = 0;
break;
case '-':
// last char is repeated 4 times
chars = new char[4];
Arrays.fill(chars, lastChar);
searchTokens.add(String.valueOf(chars));
lastChar = 0;
break;
default:
if (lastChar != 0) {
searchTokens.add(String.valueOf(lastChar));
}
lastChar = c;
}
}
return searchTokens.toArray(new String[searchTokens.size()]);
}
}
输出：
Needles: [aa, bb, cccc]
Found: 4
Needles: [a, bb, cccc]
Found: 18
非递归算法，需要 O(m) space 并在 O(n*m) 中运行，其中 m 是查询中的标记数：
@Test
public void subequences() {
String input = "aabbccaacccccbbd";
String query = "a+b+";
// here to store tokens of a query: e.g. {a, +}, {b, +}
char[][] q = new char[query.length() / 2][];
// here to store counts of subsequences ending by j-th token found so far
int[] c = new int[query.length() / 2]; // main
int[] cc = new int[query.length() / 2]; // aux
// tokenize
for (int i = 0; i < query.length(); i += 2)
q[i / 2] = new char[] {query.charAt(i), query.charAt(i + 1)};
// init
char[] sub2 = {0, 0}; // accumulator capturing last 2 chars
char[] sub4 = {0, 0, 0, 0}; // accumulator capturing last 4 chars
// main loop
for (int i = 0; i < input.length(); i++) {
shift(sub2, input.charAt(i));
shift(sub4, input.charAt(i));
boolean all2 = sub2[1] != 0 && sub2[0] == sub2[1]; // true if all sub2 chars are same
boolean all4 = sub4[3] != 0 && sub4[0] == sub4[1] // true if all sub4 chars are same
&& sub4[0] == sub4[2] && sub4[0] == sub4[3];
// iterate tokens
for (int j = 0; j < c.length; j++) {
if (all2 && q[j][1] == '+' && q[j][0] == sub2[0]) // found match for "+" token
cc[j] = j == 0 // filling up aux array
? c[j] + 1 // first token, increment counter by 1
: c[j] + c[j - 1]; // add value of preceding token counter
if (all4 && q[j][1] == '-' && q[j][0] == sub4[0]) // found match for "-" token
cc[j] = j == 0
? c[j] + 1
: c[j] + c[j - 1];
}
if (all2) sub2[1] = 0; // clear, to make "aa" occur in "aaaa" 2, not 3 times
if (all4) sub4[3] = 0;
copy(cc, c); // copy aux array to main
}
}
System.out.println(c[c.length - 1]);
}
// shifts array 1 char left and puts c at the end
void shift(char[] cc, char c) {
for (int i = 1; i < cc.length; i++)
cc[i - 1] = cc[i];
cc[cc.length - 1] = c;
}
// copies array contents
void copy(int[] from, int[] to) {
for (int i = 0; i < from.length; i++)
to[i] = from[i];
}
主要思想是从输入中一个一个地捕获字符，将它们保存在 2 字符和 4 字符的累加器中，并检查它们是否与查询的某些标记匹配，记住我们得到了多少匹配项到目前为止以这些标记结尾的子查询。
查询 (a+b+c-) 被拆分为标记 (a+、b+、c-)。然后我们在累加器中收集字符并检查它们是否匹配某些标记。如果我们找到第一个标记的匹配项，我们将其计数器加 1。如果我们找到另一个 j-th 标记 的匹配项，我们可以创建与 子查询匹配的其他子序列由标记 [0...j] 组成，因为现在存在许多标记 对于由标记 [0...j-1] 组成的子查询，因为此匹配可以附加到它们中的每一个。
例如，我们有：
a+ : 3 (3 matches for a+)
b+ : 2 (2 matches for a+b+)
c- : 1 (1 match for a+b+c-)
cccc 到达时。然后 c- 计数器应该增加 b+ 计数器值，因为到目前为止我们有 2 个 a+b+ 子序列并且 cccc 可以附加到它们。
如果您首先使用简单的 parser/compiler 转换搜索字符串，因此 a+ 变为 aa 等，那么您可以简单地使用此字符串和 运行 一个正则表达式与你的干草堆相匹配。 （抱歉，我不是 Java 程序员，所以无法提供任何真正的代码，但这并不难）