Text :: Make Part After AND Not Match Already Matched First Part?

I have a table of addresses where the indexed column consists of the city, an optional area name, the street name and the street number. For example 'Stockholm Drottninggatan 2'.

The users must enter the full city name and the beginning of the street name. So if the user wants to find all the addresses of both the streets Stockrosvägen and Stockbergsvägen which are in Stockholm, the query would look something like this:

Select * From AddressSearch
Where Contains(AddressSearch.Address, 'Stockholm AND Stock%') > 0;

But this will select all the addresses of Stockholm. Is there a way to make the part after the AND not match the already matched first part?