Regarding a data structure for O(1) get on prefixes

Question

So I am trying to write a little utility in Scala that constantly listens on a bunch of directories for file system changes (deletes, creates, modifications etc) and rsyncs it immediately across to a remote server. (https://github.com/Khalian/LockStep)

My configurations are stored in JSON as the follows:-

{
  "localToRemoteDirectories": {
    "/workplace/arunavs/third_party": {
      "remoteDir": "/remoteworkplace/arunavs/third_party",
      "remoteServerAddr": "some Remote server address"
    }
  } 
}

This configuration is stored in a Scala Map (key = localDir, value = (remoteDir, remoteServerAddr)). The tuple is represented as a case class

sealed case class RemoteLocation(remoteDir:String, remoteServerAddr:String)

I am using an actor from a third party:

https://github.com/lloydmeta/schwatcher/blob/master/src/main/scala/com/beachape/filemanagement/FileSystemWatchMessageForwardingActor.scala) 

that listens on these directories (e.g. /workplace/arunavs/third_party and then outputs an Java 7 WatchKind event (EVENT_CREATE, EVENT_MODIFY etc). The problem is that the events sent are absolute path (for instance if I create a file helloworld in third_party dir, the message sent by the actor is (ENTRY_CREATE, /workplace/arunavs/third_party/helloworld))

I need a way to write a getter that gets the nearest prefix from the configuration map stored above. The obvious way to do it is to filter on the map:-

def getRootDirsAndRemoteAddrs(localDir:String) : Map[String, RemoteLocation] =
    localToRemoteDirectories.filter(e => localDir.startsWith(e._1))

This simply returns the subset of keys that are a prefix to the localDir (in the above example this method is called with localDir = /workplace/arunavs/third_party/helloworld. While this works, this implementation is O(n) where n is the number of items in my configuration. I am looking for better computational complexity (I looked at radix and patricia tries, but they dont cut it since I feeding a string and trying to get keys which are prefixes to it, tries solve the opposite problem).