Debian does that via the website:
- search the Packages page under Search contents of packages
- the answer in this example
- options selected where 'packages that contain files whose name contain the keyword' for the unstable distribution (as it is the largest) on 'any' architecture
Ubuntu probably does something similar but I don't know the website / launchpad that well.
You could also fetch the index file ftp://ftp.us.debian.org/debian/dists/sid/Contents-i386.gz
but as it changes frequently the website option is probably more convenient.