This patch is based on
http://tools.suckless.org/dmenu/patches/dmenu_xmms.diff

diff -up dmenu-4.1.1/config.def.h dmenu-4.1.1_xmms/config.def.h
--- dmenu-4.1.1/config.def.h	2009-04-18 13:50:04.000000000 +0200
+++ dmenu-4.1.1_xmms/config.def.h	2009-11-19 21:31:17.000000000 +0100
@@ -7,3 +7,4 @@ static const char *normfgcolor = "#00000
 static const char *selbgcolor  = "#0066ff";
 static const char *selfgcolor  = "#ffffff";
 static unsigned int spaceitem  = 30; /* px between menu items */
+static unsigned int maxtokens  = 16; /* max. tokens for pattern matching */
diff -up dmenu-4.1.1/dmenu.1 dmenu-4.1.1_xmms/dmenu.1
--- dmenu-4.1.1/dmenu.1	2009-04-18 13:50:04.000000000 +0200
+++ dmenu-4.1.1_xmms/dmenu.1	2009-11-19 21:14:24.000000000 +0100
@@ -11,6 +11,7 @@ dmenu \- dynamic menu
 .RB [ \-p " <prompt>"]
 .RB [ \-sb " <color>"]
 .RB [ \-sf " <color>"]
+.RB [ \-xs ]
 .RB [ \-v ]
 .SH DESCRIPTION
 .SS Overview
@@ -44,6 +45,9 @@ defines the selected background color (#
 .B \-sf <color>
 defines the selected foreground color (#RGB, #RRGGBB, and color names are supported).
 .TP
+.B \-xs
+xmms-like pattern matching.
+.TP
 .B \-v
 prints version information to standard output, then exits.
 .SH USAGE
diff -u dmenu-4.1.1/dmenu.c.orig dmenu-4.1.1/dmenu.c
--- dmenu-4.1.1/dmenu.c.orig	2010-05-29 13:56:51.000000000 +0200
+++ dmenu-4.1.1/dmenu.c	2010-07-05 22:23:30.000000000 +0200
@@ -75,6 +75,7 @@
 /* variables */
 static char *maxname = NULL;
 static char *prompt = NULL;
+static char **tokens = NULL;
 static char text[4096];
 static int cmdw = 0;
 static int promptw = 0;
@@ -84,6 +85,7 @@
 static unsigned int mw, mh;
 static unsigned int numlockmask = 0;
 static Bool running = True;
+static Bool xmms = False;
 static Display *dpy;
 static DC dc;
 static Item *allitems = NULL;  /* first of all items */
@@ -578,22 +580,55 @@
 	drawmenu();
 }
 
+unsigned int tokenize(char *pat, char **tok)
+{
+	unsigned int i = 0;
+	char tmp[4096] = {0};
+
+	strncpy(tmp, pat, strlen(pat));
+	tok[0] = strtok(tmp, " ");
+
+	while(tok[i] && i < maxtokens)
+		tok[++i] = strtok(NULL, " ");
+	return i;
+}
+
 void
 match(char *pattern) {
-	unsigned int plen;
+	unsigned int plen, tokencnt = 0;
+	char append = 0;
 	Item *i, *itemend, *lexact, *lprefix, *lsubstr, *exactend, *prefixend, *substrend;
 
 	if(!pattern)
 		return;
-	plen = strlen(pattern);
+
+	if(!xmms)
+		tokens[(tokencnt = 1)-1] = pattern;
+	else
+		if(!(tokencnt = tokenize(pattern, tokens)))
+			tokens[(tokencnt = 1)-1] = "";
 	item = lexact = lprefix = lsubstr = itemend = exactend = prefixend = substrend = NULL;
-	for(i = allitems; i; i = i->next)
-		if(!fstrncmp(pattern, i->text, plen + 1))
+	for(i = allitems; i; i = i->next) {
+		for(int j = 0; j < tokencnt; ++j) {
+			plen = strlen(tokens[j]);
+			if(!fstrncmp(tokens[j], i->text, plen + 1))
+				append = !append || append > 1 ? 1 : append;
+			else if(!fstrncmp(tokens[j], i->text, plen ))
+				append = !append || append > 2 ? 2 : append;
+			else if(fstrstr(i->text, tokens[j]))
+				append = append > 0 && append < 3 ? append : 3;
+			else {
+				append = 0;
+				break;
+			}
+		}
+		if(append == 1)
 			appenditem(i, &lexact, &exactend);
-		else if(!fstrncmp(pattern, i->text, plen))
+		else if(append == 2)
 			appenditem(i, &lprefix, &prefixend);
-		else if(fstrstr(i->text, pattern))
+		else if(append == 3)
 			appenditem(i, &lsubstr, &substrend);
+	}
 	if(lexact) {
 		item = lexact;
 		itemend = exactend;
@@ -748,6 +783,7 @@
 	if(prompt)
 		promptw = MIN(textw(prompt), mw / 5);
 	text[0] = '\0';
+	tokens = malloc((xmms?maxtokens:1)*sizeof(char*));
 	match(text);
 	XMapRaised(dpy, win);
 }
@@ -806,11 +842,13 @@
 		else if(!strcmp(argv[i], "-sf")) {
 			if(++i < argc) selfgcolor = argv[i];
 		}
+		else if(!strcmp(argv[i], "-xs"))
+			xmms = True;
 		else if(!strcmp(argv[i], "-v"))
 			eprint("dmenu-"VERSION", © 2006-2010 dmenu engineers, see LICENSE for details\n");
 		else
 			eprint("usage: dmenu [-i] [-b] [-e <xid>] [-l <lines>] [-fn <font>] [-nb <color>]\n"
-			       "             [-nf <color>] [-p <prompt>] [-sb <color>] [-sf <color>] [-v]\n");
+			       "             [-nf <color>] [-p <prompt>] [-sb <color>] [-sf <color>] [-xs] [-v]\n");
 	if(!setlocale(LC_CTYPE, "") || !XSupportsLocale())
 		fprintf(stderr, "warning: no locale support\n");
 	if(!(dpy = XOpenDisplay(NULL)))