查找给定字符串中所有出现的字符串作为子序列 [英] Find all the occurences of a string as a subsequence in a given string

问题描述

给定字符串A和B，找到A中所有出现的B作为子序列.

Given strings A and B, find all the occurrences of B in A as a subsequence.

示例:

A =mañanade lamañana"

A = "mañana de la mañana"

B =玛娜娜娜"

答案:

0-> 玛娜娜德拉玛娜娜

1-> 玛娜 a de l a 玛娜娜

1 -> mañana de la mañana

2-> ma​​ñ ana de lamañ ana

2 -> mañana de la mañana

...

基于一种算法，我在此处计算出现的次数，其中有16次.我需要找到所有此类子序列并报告其索引的算法.

Based on an algorithm I found here which counts the number of occurrences there are 16 of those. I need an algorithm that finds all such subsequences and reports their indices.

推荐答案

基本的递归就像

/** 
 * @param  {[type]} iA current letter index in A
 * @param  {[type]} iB current letter index in B
 */ 
function rec (A, B, iA, iB, indices, solutions) {
  if (iB === B.length) {
    // copy the array if solution
    solutions.push(indices.slice(0))
    return
  }
  if (iA === A.length) {
    return
  }
  const cb = B[iB]
  // find all occurrences of cb in A
  for (let i = iA; i < A.length; ++i) {
    const ca = A[i]
    if (ca === cb) {
      indices[iB] = i
      //match the next char
      rec(A, B, i + 1, iB + 1, indices, solutions)
    }
  }
}
const A = "mañana de la mañana"
const B = "mañana"
const solutions = []
rec(A, B, 0, 0, [], solutions)
console.log(solutions.map(x => [
  x.join(','), A.split('').map((c, i) => x.includes(i) ? c.toUpperCase() : c).join('')
]))

对于动态方法

• 构建所有以m结尾的序列并将其存储到S_m
• 从S_m构建所有以a结尾的序列并将其存储到S_{ma}
• 依此类推

• build all sequences ending in m and store them to S_m
• build all sequences ending in a from S_m and store them to S_{ma}
• and so forth

const A = "mañana de la mañana"
const B = "mañana"
let S = A.split('').flatMap((a, i) => a === B[0] ? [[i]] : [])
// S is initially [ [0], [13] ]
B.split('').slice(1).forEach(b => {
  const S_m = []
  S.forEach(s => {
    const iA = s[s.length - 1]
    // get the last index from current sequence
    // and look for next char in A starting from that index
    for (let i = iA + 1; i < A.length; ++i) {
      const ca = A[i]
      if (ca === b) {
        S_m.push(s.concat(i))
      }
    }
  })
  S = S_m
})
console.log(S.map(x => [
  x.join(','), A.split('').map((c, i) => x.includes(i) ? c.toUpperCase() : c).join('')
]))

这篇关于查找给定字符串中所有出现的字符串作为子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！