it is interesting how much it hurts. for boyer-moore, it costs about 10% in practice. for egrep, it costs nothing as you simply duplicate entries in a jump table. for fgrep, it costs only 3-5% as you only have to map case for nodes other than the root which, at least in the new grep, is a jump table.