One idea is to use a '2 x N' array in order to store the start and end positions for each line in that string:
Array[0,k-1] = start position of line k in your string
Array[1,k-1] = end position of line k in your string
Thus, you can access easier every line you want (line i - substring starting at A[0,i-1] and (A[1,i-1]-A[0,i-1]) length) or multiple lines at a time (similar, using the end position of the last line), without searching.
Hope this helps somehow.