For some projects I often type in a couple commands, like for example:

cd an/extremely/long/path/in/which/I/have/some/kinda/project

and

./runmyproject --with some --command line --options set

Seeing that I'm pretty lazy I try to avoid typing those commands in full again and again. So I can of course use the up-key a lot to find back those commands, but often, I also have so many commands in between, that searching for it takes even more time than just typing it.

I now wonder if there is some kind of utility that can suggest a full command which I use a lot, when I haven't typed all of it yet. So that I can for example type 'cd an/' and that it already suggests the rest of the path because I've used it so much the past month.

I did find something called Bash Smart Complete. But that is a little "dumb" in that it doesn't look at the commands I used before. I just also found this SO answer, which suggests putting the commands I use a lot in a file. That however, is not responsive enough in that I would need to create a new file for it every time I start new projects or change folders or program arguments.

Does anybody know any other utility or other way to achieve this? Or, would anybody know how I could alter the Bash Smart Complete so that it can look at the commands I used in say the past month and complete the command which fits and has been used the most in the past month?

[EDIT]
Below are some really great answers. I haven marked any as a definite answer yet. Not because I do not like the answers, I do, but because none of them is an absolute winner. I think the Finalterm is a great project. Unfortunately it is still rather rough around the edges. For example; it doesn't support copy-paste yet. I would keep on eye on that project though, because when it will mature I think it'll be a great terminal app. As for the other answers; they either suggested creating an alias, which is not what I want to do because it creates extra work instead of taking work away, or using Ctrl+R, which is a brilliant (I didn't know about it!). A couple of people suggested using Ctrl+R, so I can't really highlight one answer over the other.

So for now I am definitely using Ctrl+R, and in the future I might use Finalterm.

Thanks for all the great answers guys!