CODEWITHSUNDEEP
algorithmdynamic-programming
Wildhammer
Wildhammer

Reputation: 2175

Find all the occurences of a string as a subsequence in a given string

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

Example:

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

B = "mañana"

Answer:

0 -> mañana de la mañana

1 -> mañana de la mañana

2 -> mañana de la mañana

...

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.

Upvotes: 1

Views: 482

Answers (1)

grodzi
grodzi

Reputation: 5703

The basic recursion be like

/** 
 * @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('')
]))

For the dynamic approach

  • 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('')
]))

Upvotes: 1

Related Questions