Stop-and-move semantic trajectories are segmented trajectories where the stops and moves are semantically enriched with additional data. A query language for semantic trajectory datasets has to include selectors for stops or moves based on their enrichments and sequence expressions that define how to match the results of selectors with the sequence the semantic trajectory defines. This article addresses the problem of searching semantic trajectories, using stop-and-move sequence expressions. The article first proposes a formal framework to define semantic trajectories and introduces stop-and-move sequence expressions, with well-defined syntax and semantics, which act as an expressive query language for semantic trajectories. Then, it describes a concrete semantic trajectory model in RDF, defines SPARQL stop-and-move sequence expressions and discusses strategies to compile such expressions into SPARQL queries. Lastly, the article specifies user-friendly keyword search expressions over semantic trajectories based on the use of keywords to specify stop-and-move queries, and the adoption of terms with predefined semantics to compose sequence expressions. It then shows how to compile such keyword search expressions into SPARQL queries. Finally, it provides a proof-of-concept experiment over a semantic trajectory dataset constructed with user-generated content from Flickr, combined with Wikipedia data.