Which option is better to search in two tables in varchar columns? I have a performance problem with searching in varchar columns in SQL Server 2016. Considering these tables have plenty of rows, for example 60000 rows each one. 

Tables

CREATE TABLE Persons (
PersonID int,
LastName varchar(255),
FirstName varchar(255),
CityID int)

CREATE TABLE Cities(
CityID int,
CityName varchar(255))


Code

I have a problem like this:

SELECT p.PersonID, p.FirstName , c.CityID,c.CityName  FROM PERSONS p
JOIN CITIES c ON c.CityID = p.CityID 
WHERE 
     p.FirstName like '%'+@search+'%' 
  OR p.LastName  like '%'+@search+'%' 
  OR c.CityName  like '%'+@search+'%'


Possible Solutions in my mind:


Creating a full text index for each table.
Creating Columnstore indexes.
Replicating the columns to another table and searching there.


I've searched in books like: "SQL Server 2012 Query Peformance Tunning" and "Expert Peformance Indexing for SQL Server 2012". And of course, a lot of sites and blogs on the internet.I would appreciate another suggestions to solve this issue.
Paul White wrote this article about using a trigram wildcard string search in place of the LIKE operator. It's quite an in-depth article, but it's probably the best you'll find on the subject (like a lot of what Paul White writes). I've implemented it in a test environment and it really is lightning fast compared to the LIKE operator.