查找string中子序列的出现次数

例如，让string为pi的前10位， 3141592653 ，子序列为123 。 请注意，该序列发生两次：

 3141592653 1 2 3 1 2 3 

这是一个面试问题，我无法回答，我想不出一个有效的algorithm，它是在扰乱我。 我觉得应该可以做一个简单的正则expression式，但像1.*2.*3不返回每个子序列。 我在Python中的天真执行（在每个1之后每个2计数3）已经运行了一个小时，没有完成。

Answer 1

这是一个经典的dynamic规划问题（通常不是使用正则expression式解决的）。

我天真的执行（每个1之后每个2计数3）已经运行了一个小时，没有完成。

这将是一个彻底的search方法，在指数时间运行。 （我很惊讶它运行了几个小时，但）。

---

这是一个dynamic编程解决scheme的build议：

大纲的recursion解决scheme：

（道歉很长的描述，但每一步真的很简单，所以忍受我;-)

• 如果子序列是空的，find一个匹配（没有数字留下匹配！），我们返回1

• 如果input序列是空的，我们已经耗尽了我们的数字，并且不可能find匹配，因此我们返回0

• （序列和子序列都是空的。）

• （假设“ abcdef ”表示input序列，“ xyz ”表示子序列）。

• 将result设置为0

• 添加result为bcdef和xyz的匹配数（即丢弃第一个input数字和recursion）

• 如果前两位数字匹配，即a = x

  • 添加result bcdef和yz匹配的数量（即，匹配第一个子序列数字和recursion剩余的子序列数字）

• 返回result

---

例

下面是对input1221/12的recursion调用的示例。 （以粗体显示的子序列，·表示空string。）

---

dynamic编程

如果天真地执行，一些（子）问题将被多次解决（例如上面的例子中的/ 2）。 dynamic规划通过记住先前解决的子问题（通常在查找表中）的结果来避免这种冗余计算。

在这个特定的情况下，我们build立了一个表格

• [序列长度+ 1]行，和
• [子序列的长度+ 1]列：

这个想法是我们应该在相应的行/列中填写221/2的匹配数。 一旦完成，我们应该在1221/12单元中有最终的解决scheme。

我们开始用立即知道的（“基本情况”）填充表格：

• 当没有子序列数字时，我们有1个完全匹配：

• 当没有序列号码时，我们不能有任何匹配：

  

然后按照以下规则从上到下/从左到右填充表格：

• 在单元格[ row ] [ col ]中写入在[ row -1] [col]中find的值。

  直观地说，这意味着“ 221/2 的匹配数包括21/2的所有匹配”。

• 如果在行列和列列处的序列以相同的数字开始，则将在[ 行 -1] [ 列 -1]处find的值添加到刚刚写入[ 行 ] [ 列 ]的值。

  直观上这意味着“1221/12的比赛数量还包括221/12的所有比赛。”

最终结果如下：

而右下angular的单元格的值确实是2。

---

在代码中

不是Python，（我的道歉）。

 class SubseqCounter { String seq, subseq; int[][] tbl; public SubseqCounter(String seq, String subseq) { this.seq = seq; this.subseq = subseq; } public int countMatches() { tbl = new int[seq.length() + 1][subseq.length() + 1]; for (int row = 0; row < tbl.length; row++) for (int col = 0; col < tbl[row].length; col++) tbl[row][col] = countMatchesFor(row, col); return tbl[seq.length()][subseq.length()]; } private int countMatchesFor(int seqDigitsLeft, int subseqDigitsLeft) { if (subseqDigitsLeft == 0) return 1; if (seqDigitsLeft == 0) return 0; char currSeqDigit = seq.charAt(seq.length()-seqDigitsLeft); char currSubseqDigit = subseq.charAt(subseq.length()-subseqDigitsLeft); int result = 0; if (currSeqDigit == currSubseqDigit) result += tbl[seqDigitsLeft - 1][subseqDigitsLeft - 1]; result += tbl[seqDigitsLeft - 1][subseqDigitsLeft]; return result; } } 

---

复杂

这种“填表式”方法的好处在于，找出复杂性是微不足道的。 为每个单元格完成一个恒定的工作量，并且我们有长度序列行和长度的子序列列。 O（MN）其中M和N表示序列的长度。

Answer 2

很好的答案， aioobe ！ 以补充您的答案，在Python中的一些可能的实现：

 # straightforward, naïve solution; too slow! def num_subsequences(seq, sub): if not sub: return 1 elif not seq: return 0 result = num_subsequences(seq[1:], sub) if seq[0] == sub[0]: result += num_subsequences(seq[1:], sub[1:]) return result # top-down solution using explicit memoization def num_subsequences(seq, sub): m, n, cache = len(seq), len(sub), {} def count(i, j): if j == n: return 1 elif i == m: return 0 k = (i, j) if k not in cache: cache[k] = count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0) return cache[k] return count(0, 0) # top-down solution using the lru_cache decorator # available from functools in python >= 3.2 from functools import lru_cache def num_subsequences(seq, sub): m, n = len(seq), len(sub) @lru_cache(maxsize=None) def count(i, j): if j == n: return 1 elif i == m: return 0 return count(i+1, j) + (count(i+1, j+1) if seq[i] == sub[j] else 0) return count(0, 0) # bottom-up, dynamic programming solution using a lookup table def num_subsequences(seq, sub): m, n = len(seq)+1, len(sub)+1 table = [[0]*n for i in xrange(m)] def count(iseq, isub): if not isub: return 1 elif not iseq: return 0 return (table[iseq-1][isub] + (table[iseq-1][isub-1] if seq[m-iseq-1] == sub[n-isub-1] else 0)) for row in xrange(m): for col in xrange(n): table[row][col] = count(row, col) return table[m-1][n-1] # bottom-up, dynamic programming solution using a single array def num_subsequences(seq, sub): m, n = len(seq), len(sub) table = [0] * n for i in xrange(m): previous = 1 for j in xrange(n): current = table[j] if seq[i] == sub[j]: table[j] += previous previous = current return table[n-1] if n else 1 

Answer 3

其中一种方法是使用两个列表。 叫他们和OneTwos 。

穿过string，逐字符。

• 每当看到数字1 ，在Ones列表中input一个条目。
• 每当看到数字2 ，都要通过Ones列表并将条目添加到OneTwos列表中。
• 每当看到数字3 ，通过OneTwos列表并输出一个123 。

在通常的情况下，algorithm会非常快，因为它是一个单一的通过string和多次通过通常会小得多的列表。 虽然病理性的病例会杀死它。 设想一个像111111222222333333这样的string，但每个数字重复数百次。

Answer 4

 from functools import lru_cache def subseqsearch(string,substr): substrset=set(substr) #fixs has only element in substr fixs = [i for i in string if i in substrset] @lru_cache(maxsize=None) #memoisation decorator applyed to recs() def recs(fi=0,si=0): if si >= len(substr): return 1 r=0 for i in range(fi,len(fixs)): if substr[si] == fixs[i]: r+=recs(i+1,si+1) return r return recs() #test from functools import reduce def flat(i) : return reduce(lambda x,y:x+y,i,[]) N=5 string = flat([[i for j in range(10) ] for i in range(N)]) substr = flat([[i for j in range(5) ] for i in range(N)]) print("string:","".join(str(i) for i in string),"substr:","".join(str(i) for i in substr),sep="\n") print("result:",subseqsearch(string,substr)) 

输出（即时）：

 string: 00000000001111111111222222222233333333334444444444 substr: 0000011111222223333344444 result: 1016255020032 

Answer 5

我的快速尝试：

 def count_subseqs(string, subseq): string = [c for c in string if c in subseq] count = i = 0 for c in string: if c == subseq[0]: pos = 1 for c2 in string[i+1:]: if c2 == subseq[pos]: pos += 1 if pos == len(subseq): count += 1 break i += 1 return count print count_subseqs(string='3141592653', subseq='123') 

编辑：这一个应该是正确的，如果1223 == 2和更复杂的情况下：

 def count_subseqs(string, subseq): string = [c for c in string if c in subseq] i = 0 seqs = [] for c in string: if c == subseq[0]: pos = 1 seq = [1] for c2 in string[i + 1:]: if pos > len(subseq): break if pos < len(subseq) and c2 == subseq[pos]: try: seq[pos] += 1 except IndexError: seq.append(1) pos += 1 elif pos > 1 and c2 == subseq[pos - 1]: seq[pos - 1] += 1 if len(seq) == len(subseq): seqs.append(seq) i += 1 return sum(reduce(lambda x, y: x * y, seq) for seq in seqs) assert count_subseqs(string='12', subseq='123') == 0 assert count_subseqs(string='1002', subseq='123') == 0 assert count_subseqs(string='0123', subseq='123') == 1 assert count_subseqs(string='0123', subseq='1230') == 0 assert count_subseqs(string='1223', subseq='123') == 2 assert count_subseqs(string='12223', subseq='123') == 3 assert count_subseqs(string='121323', subseq='123') == 3 assert count_subseqs(string='12233', subseq='123') == 4 assert count_subseqs(string='0123134', subseq='1234') == 2 assert count_subseqs(string='1221323', subseq='123') == 5 

Answer 6

PSH。 O（n）解决scheme更好。

想想通过build立一棵树：

如果字符是'1'，则沿着string迭代，向树的根部添加一个节点。 如果字符是'2'，则向每个第一级节点添加一个子节点。 如果字符是'3'，则为每个第二级节点添加一个子节点。

返回第三层节点的数量。

这将是空间效率低下，为什么我们不只是存储每个深度的节点数量：

 infile >> in; long results[3] = {0}; for(int i = 0; i < in.length(); ++i) { switch(in[i]) { case '1': results[0]++; break; case '2': results[1]+=results[0]; break; case '3': results[2]+=results[1]; break; default:; } } cout << results[2] << endl; 

Answer 7

如何计算数字数组中的所有三元序列1..2..3。

快速，简单

注意，我们不需要find所有的序列，我们只需要COUNT它们。 所以，所有search序列的algorithm都过于复杂。

1. 扔掉每个数字，不是1,2,3。 结果将是字符数组A
2. 制作0的并行int数组B. 最后运行A，计算A中的每2个A之后的A个中的3个。 把这些数字放入B的适当元素
3. 使平行的int数组C为0。从A中的每个1的结束计数运行A在其位置之后的B的总和。 结果放到了C的适当位置
4. 计算C的总和

就这些。 复杂性是O（N）。 真的，对于正常的数字行来说，它将花费两倍的缩短源线的时间。

如果顺序会比较长，例如M个成员，那么程序可以重复M次。 复杂度将是O（MN），其中N已经是缩短的源string的长度。

Answer 8

我对这个问题有一个有趣的O（N）时间和O（M）空间解决scheme 。
N是文本的长度，M是要search的模式的长度。 我将向你解释algorithm，因为我用C ++实现。

让我们假设给定的input是你提供的3141592653和计数find的模式序列是123。 我将从一个散列图开始，它将字符映射到它们在input模式中的位置。 我还取一个初始化为0的大小为M的数组。

  string txt,pat; cin >> txt >> pat; int n = txt.size(),m = pat.size(); int arr[m]; map<char,int> mp; map<char,int> ::iterator it; f(i,0,m) { mp[pat[i]] = i; arr[i] = 0; } 

我开始从后面查找元素，并检查每个元素是否在模式中。 如果这个元素是在模式中。 我需要做一些事情。

现在当我开始从后面看，如果我find一个2和以前我还没有find任何3。 这2个对我们来说没有任何价值。因为任何1个被发现后都会形成这样的序列12和123不会形成Ryt？ 认为。 同样在目前的位置，我已经find了一个2，它将形成序列123只有以前发现3，并将形成x序列，如果我们发现x 3之前（如果部分序列之前2将被发现）ryt？ 所以完整的algorithm是每当我find一个存在于数组中的元素时，我就会相应地检查它存在于模式中的位置j（存储在哈希映射中）。 我只是增加

  arr[j] += arr[j+1]; 

这意味着它将有助于在它之前发现的3个序列？ 如果j发现是m-1，我会简单地增加它

  arr[j] += 1; 

检查下面的代码片段

  for(int i = (n-1);i > -1;i--) { char ch = txt[i]; if(mp.find(ch) != mp.end()) { int j = mp[ch]; if(j == (m-1)) arr[j]++; else if(j < (m-1)) arr[j] += arr[j+1]; else {;} } } 

现在考虑这个事实

数组中的每个索引i存储模式S [i，（m-1）]的子串作为input串So的序列的次数。最后，打印arr [0]

  cout << arr[0] << endl; 

具有输出的代码（模式中的唯一字符） http://ideone.com/UWaJQF

带输出的代码（允许重复的字符） http://ideone.com/14DZh7

扩展只有在模式具有独特元素时才起作用如果模式具有独特的元素，那么复杂性可能会发生到O（MN）解决scheme类似于不使用DP只是当出现在模式中的元素出现时，我们刚刚增加对应于它的数组位置j我们现在在模式中更新所有这些字符的出现，这将导致复杂度为O（字符的N *最大频率）

 #define f(i,x,y) for(long long i = (x);i < (y);++i) int main() { long long T; cin >> T; while(T--) { string txt,pat; cin >> txt >> pat; long long n = txt.size(),m = pat.size(); long long arr[m]; map<char,vector<long long> > mp; map<char,vector<long long> > ::iterator it; f(i,0,m) { mp[pat[i]].push_back(i); arr[i] = 0; } for(long long i = (n-1);i > -1;i--) { char ch = txt[i]; if(mp.find(ch) != mp.end()) { f(k,0,mp[ch].size()) { long long j = mp[ch][k]; if(j == (m-1)) arr[j]++; else if(j < (m-1)) arr[j] += arr[j+1]; else {;} } } } cout <<arr[0] << endl; } } 

可以以类似的方式进行扩展，没有重复的string中的DP，但是复杂性会更多O（MN）