diff --git a/autotests/CMakeLists.txt b/autotests/CMakeLists.txt
--- a/autotests/CMakeLists.txt
+++ b/autotests/CMakeLists.txt
@@ -33,6 +33,9 @@
 # KServiceTest::testAllServices can fail if any service is deleted while the test runs
 set_tests_properties(kservicetest PROPERTIES RUN_SERIAL TRUE)
 
+target_sources(kservicetest PUBLIC
+  ${CMAKE_CURRENT_SOURCE_DIR}/../src/services/ktraderparsetree.cpp
+)
 
 add_library(fakeplugin MODULE nsaplugin.cpp)
 ecm_mark_as_test(fakeplugin)
diff --git a/autotests/kservicetest.h b/autotests/kservicetest.h
--- a/autotests/kservicetest.h
+++ b/autotests/kservicetest.h
@@ -39,6 +39,7 @@
     void testAllServices();
     void testServiceTypeTraderForReadOnlyPart();
     void testTraderConstraints();
+    void testSubseqConstraints();
     void testHasServiceType1();
     void testHasServiceType2();
     void testWriteServiceTypeProfile();
diff --git a/autotests/kservicetest.cpp b/autotests/kservicetest.cpp
--- a/autotests/kservicetest.cpp
+++ b/autotests/kservicetest.cpp
@@ -28,6 +28,7 @@
 #include <ksycoca.h>
 #include <kbuildsycoca_p.h>
 #include <../src/services/kserviceutil_p.h>
+#include <../src/services/ktraderparsetree_p.h>
 
 #include <kservicegroup.h>
 #include <kservicetypetrader.h>
@@ -545,6 +546,16 @@
     QCOMPARE(offers.count(), 1);
     QVERIFY(offerListHasService(offers, QStringLiteral("faketextplugin.desktop")));
 
+    // sub-sequence case sensitive
+    offers = KServiceTypeTrader::self()->query(QStringLiteral("FakePluginType"), QStringLiteral("'txtlug' subseq Library"));
+    QCOMPARE(offers.count(), 1);
+    QVERIFY(offerListHasService(offers, QStringLiteral("faketextplugin.desktop")));
+
+    // sub-sequence case insensitive
+    offers = KServiceTypeTrader::self()->query(QStringLiteral("FakePluginType"), QStringLiteral("'tXtLuG' ~subseq Library"));
+    QCOMPARE(offers.count(), 1);
+    QVERIFY(offerListHasService(offers, QStringLiteral("faketextplugin.desktop")));
+
     if (m_hasNonCLocale) {
 
         // Test float parsing, must use dot as decimal separator independent of locale.
@@ -558,6 +569,34 @@
     QVERIFY(offers.isEmpty());
 }
 
+void KServiceTest::testSubseqConstraints()
+{
+  auto test = [](const char* pattern, const char* text, bool sensitive) {
+    return KTraderParse::ParseTreeSubsequenceMATCH::isSubseq(
+        QString(pattern),
+        QString(text),
+        sensitive? Qt::CaseSensitive : Qt::CaseInsensitive
+    );
+  };
+
+  // Case Sensitive
+  QVERIFY2(!test("", "", 1), "both empty");
+  QVERIFY2(!test("", "something", 1), "empty pattern");
+  QVERIFY2(!test("something", "", 1), "empty text");
+  QVERIFY2(test("lngfile", "somereallylongfile", 1), "match ending");
+  QVERIFY2(test("somelong", "somereallylongfile", 1), "match beginning");
+  QVERIFY2(test("reallylong", "somereallylongfile", 1), "match middle");
+  QVERIFY2(test("across", "a 23 c @#! r o01 o 5 s_s", 1), "match across");
+  QVERIFY2(!test("nocigar", "soclosebutnociga", 1), "close but no match");
+  QVERIFY2(!test("god", "dog", 1), "incorrect letter order");
+  QVERIFY2(!test("mismatch", "mIsMaTcH", 1), "case sensitive mismatch");
+
+  // Case insensitive
+  QVERIFY2(test("mismatch", "mIsMaTcH", 0), "case insensitive match");
+  QVERIFY2(test("tryhards", "Try Your Hardest", 0), "uppercase text");
+  QVERIFY2(test("TRYHARDS", "try your hardest", 0), "uppercase pattern");
+}
+
 void KServiceTest::testHasServiceType1() // with services constructed with a full path (rare)
 {
     QString fakepartPath = QStandardPaths::locate(QStandardPaths::GenericDataLocation, QLatin1String("kservices5/") + "fakepart.desktop");
diff --git a/src/services/ktraderparse.cpp b/src/services/ktraderparse.cpp
--- a/src/services/ktraderparse.cpp
+++ b/src/services/ktraderparse.cpp
@@ -101,6 +101,11 @@
     return new ParseTreeMATCH(static_cast<ParseTreeBase *>(_ptr1), static_cast<ParseTreeBase *>(_ptr2), _cs == 1 ? Qt::CaseSensitive : Qt::CaseInsensitive);
 }
 
+void *KTraderParse_newSubsequenceMATCH(void *_ptr1, void *_ptr2, int _cs)
+{
+  return new ParseTreeSubsequenceMATCH(static_cast<ParseTreeBase *>(_ptr1), static_cast<ParseTreeBase *>(_ptr2), _cs == 1 ? Qt::CaseSensitive : Qt::CaseInsensitive);
+}
+
 void *KTraderParse_newCALC(void *_ptr1, void *_ptr2, int _i)
 {
     return new ParseTreeCALC(static_cast<ParseTreeBase *>(_ptr1), static_cast<ParseTreeBase *>(_ptr2), _i);
diff --git a/src/services/ktraderparse_p.h b/src/services/ktraderparse_p.h
--- a/src/services/ktraderparse_p.h
+++ b/src/services/ktraderparse_p.h
@@ -32,6 +32,7 @@
 void *KTraderParse_newIN(void *_ptr1, void *_ptr2, int _cs);
 void *KTraderParse_newSubstringIN(void *_ptr1, void *_ptr2, int _cs);
 void *KTraderParse_newMATCH(void *_ptr1, void *_ptr2, int _cs);
+void *KTraderParse_newSubsequenceMATCH(void *_ptr1, void *_ptr2, int _cs);
 void *KTraderParse_newCALC(void *_ptr1, void *_ptr2, int _i);
 void *KTraderParse_newBRACKETS(void *_ptr1);
 void *KTraderParse_newNOT(void *_ptr1);
diff --git a/src/services/ktraderparsetree.cpp b/src/services/ktraderparsetree.cpp
--- a/src/services/ktraderparsetree.cpp
+++ b/src/services/ktraderparsetree.cpp
@@ -423,6 +423,42 @@
     return true;
 }
 
+bool ParseTreeSubsequenceMATCH::eval(ParseContext *_context) const
+{
+  _context->type = ParseContext::T_BOOL;
+
+  ParseContext c1(_context);
+  ParseContext c2(_context);
+  if (!m_pLeft->eval(&c1)) {
+    return false;
+  }
+  if (!m_pRight->eval(&c2)) {
+    return false;
+  }
+  if (c1.type != ParseContext::T_STRING || c2.type != ParseContext::T_STRING) {
+    return false;
+  }
+  _context->b = ParseTreeSubsequenceMATCH::isSubseq(c1.str, c2.str, m_cs);
+  return true;
+}
+
+bool ParseTreeSubsequenceMATCH::
+isSubseq(const QString& pattern, const QString& text, Qt::CaseSensitivity cs)
+{
+  if (pattern.isEmpty()) {
+    return false;
+  }
+  bool chk_case = cs == Qt::CaseSensitive;
+
+  QString::const_iterator i = text.constBegin(), j = pattern.constBegin();
+  for (; i != text.constEnd() && j != pattern.constEnd(); ++i) {
+    if ((chk_case && *i == *j) || (!chk_case && i->toLower() == j->toLower())) {
+      ++j;
+    }
+  }
+  return j == pattern.constEnd();
+}
+
 bool ParseTreeIN::eval(ParseContext *_context) const
 {
     _context->type = ParseContext::T_BOOL;
diff --git a/src/services/ktraderparsetree_p.h b/src/services/ktraderparsetree_p.h
--- a/src/services/ktraderparsetree_p.h
+++ b/src/services/ktraderparsetree_p.h
@@ -221,6 +221,41 @@
     Qt::CaseSensitivity m_cs;
 };
 
+/**
+  * @internal
+  *
+  * A sub-sequence match is like a sub-string match except the characters
+  * do not have to be contiguous. For example 'ct' is a sub-sequence of 'cat'
+  * but not a sub-string. 'at' is both a sub-string and sub-sequence of 'cat'.
+  * All sub-strings are sub-sequences.
+  *
+  * This is useful if you want to support a fuzzier search, say for instance
+  * you are searching for `LibreOffice 6.0 Writer`, after typing `libre` you
+  * see a list of all the LibreOffice apps, to narrow down that list you only
+  * need to add `write` (so the search term is `librewrite`) instead of typing
+  * out the entire app name until a distinguishing letter is reached.
+  * It's also useful to allow the user to forget to type some characters.
+  */
+class ParseTreeSubsequenceMATCH : public ParseTreeBase
+{
+public:
+  ParseTreeSubsequenceMATCH(ParseTreeBase *_ptr1, ParseTreeBase *_ptr2, Qt::CaseSensitivity cs)
+  {
+    m_pLeft = _ptr1;
+    m_pRight = _ptr2;
+    m_cs = cs;
+  }
+
+  bool eval(ParseContext *_context) const override;
+
+  static bool isSubseq(const QString& pattern, const QString& text, Qt::CaseSensitivity cs);
+
+protected:
+  ParseTreeBase::Ptr m_pLeft;
+  ParseTreeBase::Ptr m_pRight;
+  Qt::CaseSensitivity m_cs;
+};
+
 /**
  * @internal
  */
diff --git a/src/services/lex.l b/src/services/lex.l
--- a/src/services/lex.l
+++ b/src/services/lex.l
@@ -35,6 +35,8 @@
 "<=" { return LEQ; }
 ">=" { return GEQ; }
 "~~" { return MATCH_INSENSITIVE; }
+"subseq" { return MATCH_SUBSEQUENCE; }
+"~subseq" { return MATCH_SUBSEQUENCE_INSENSITIVE; }
 "not" { return NOT; }
 "and" { return AND; }
 "or" { return OR; }
diff --git a/src/services/yacc.y b/src/services/yacc.y
--- a/src/services/yacc.y
+++ b/src/services/yacc.y
@@ -45,6 +45,8 @@
 %token TOKEN_IN
 %token TOKEN_IN_SUBSTRING
 %token MATCH_INSENSITIVE
+%token MATCH_SUBSEQUENCE
+%token MATCH_SUBSEQUENCE_INSENSITIVE
 %token TOKEN_IN_INSENSITIVE
 %token TOKEN_IN_SUBSTRING_INSENSITIVE
 %token EXIST
@@ -122,6 +124,8 @@
 
 expr_twiddle: expr '~' expr { $$ = KTraderParse_newMATCH( $<ptr>1, $<ptr>3, 1 ); }
             | expr_twiddle MATCH_INSENSITIVE expr { $$ = KTraderParse_newMATCH( $<ptr>1, $<ptr>3, 0 ); }
+            | expr_twiddle MATCH_SUBSEQUENCE expr { $$ = KTraderParse_newSubsequenceMATCH( $<ptr>1, $<ptr>3, 1 ); }
+            | expr_twiddle MATCH_SUBSEQUENCE_INSENSITIVE expr { $$ = KTraderParse_newSubsequenceMATCH( $<ptr>1, $<ptr>3, 0 ); }
             | expr { $$ = $<ptr>1; }
 ;
 
@@ -156,6 +160,7 @@
 
 void yyerror ( yyscan_t scanner, const char *s )  /* Called by yyparse on error */
 {
+    (void) scanner;
     KTraderParse_error( s );
 }