Split string using special parameters

Question

I have the following string:

1,1,1,0,1,1,2,1,1,1,1,2,1,1,1,0,1,1,0,1,1,1,

---

0-->rupture
2-->continuity

---

• When i have 1s between two 0s it means that i have a document [0,1,1,1,0] = D
• when i have 1s between a 2 and a 0 it means that i have a fragment [2,1,...,1,0] = f and i add all the fragments to a list of fragments F and it signifies the end of the sub-fragments
• when i have 1s between a 2 and a 2 it means that i also have a fragment [2,1,...,1,2] = f

---

As a solution I must have in the end :

• 3 documents D1,D2,D3 which are located between the indices [0,3], [15,18], [18,21]
• A Fragment F between [3,15] containing 3 sub-fragments , f1 between [3,6] ,f2 between [6,11] and f3 between [11,15].

Note: We consider that the string starts with a 0 and ends with a 0 This is why we have a document between [0,3] and another document between [18,21]

---

I am trying to formulate this problem but i can't come up with a solid idea. Please tell me if it is clear. and what can I use as an algorithm to help solve this problem, can I use a specific data-structure like a tree...

Thank you, Hani.

Answer 1

If your string is:

1,1,1,0,1,1,2,1,1,1,1,2,1,1,1,0,1,1,0,1,1,1

Initialize lastPos = 0, lastType = 0 {lastType = 0 for 0 and 2 for 2}

Traverse the array. You find the next 0 at position 3. Since lastType was equal to 0, you know that you have found a sequence of 1s between 2 zeroes. Do whatever.

Make lastType = 0, lastPos = 3.

Continue till the end.

Order of time complexity: O(n)
Order of space complexity: O(1)