I have a file which contains concatenated strings. 

`find_or_add(string)` either:

* returns the offset of an occurrence of the string in the file (not necessarily the first)
* adds as much of the tail of the string to the file as necessary for the file to contain the string (and then returns the offset of the string in the file).

pseudocode:

```
file.init()                // file == ""
file.find_or_add("cat")    // file == "cat", returns 0
file.find_or_add("able")   // file == "catable", returns 3
file.find_or_add("table")  // file == "catable", returns 2
file.find_or_add("tables") // file == "catables", returns 2
file.find_or_add("spigot") // file == "catablespigot", returns 7
file.find_or_add("pig")    // file == "catablespigot", returns 8

```

What algorithm/structure should I be looking at to 'summarise' this file in memory, and allow the required operations in at most O(log N)?

Assume that the file is bigger than RAM.

Language is not important, but I can read Pseudocode, C, Java, Python, Javascript and Haskell.