algorithm - Dynamic Programming total non uniform patterns idenification -

can 1 give me idea how solve following problem

input: - given string of binary numbers "1000101010101" - pattern "101" output: integer indicating possible no of non continuous patterns available

explanation:

input: "10101" output: 4

10101 10101 10101 10101

let s(0), s(1), ... given sequence of binary numbers.

let a(n), b(n), c(n) number of appearance of 1, 10, 101 in first n terms of s, respectively.

then have recurrence relation:

• if s(n) = 1, then:

  a(n) = a(n - 1) + 1, b(n) = b(n - 1), c(n) = c(n - 1) + b(n - 1).

• if s(n) = 0, then:

  a(n) = a(n- 1), b(n) = b(n - 1) + a(n - 1), c(n) = c(n - 1).

this gives o(n) algorithm, optimal, since input o(n).