I like the idea from moritz.

One aspect about this that may not be clear is that Perl can generate and use dynamic regex's "on the fly" - meaning that your code can dynamically generate a regex as a string and that regex can be used in the code later on. This "dynamic run-time generation of regex's" is a "magical feature of Perl" - and it works great!

Update:

#!/usr/bin/perl -w
use strict;

my $pattern  = "JEJE";
my $string = "EJKJUJHJDJEJEJEDEJOJOJJJAHJHJSHJEFEJUJEJUJKIJS";

# from the $pattern, generate a $regex like this:
my $regex = "JEJE|.EJE|J.JE|JE.E|JEJ.";

# and use it like this:
my (@matches) = $string =~ m/$regex/g;
print join ("\n", @matches), "\n";

__END__
prints:
JDJE
JEJE
JEFE
JUJE
[download]

I'm not sure what the desired output should be (overlapping or not).
The basic idea that I am saying is that you can generate a regex "on-the-fly" based upon some input and use it in subsequent code.

Update:
I am unsure about the fastest way (execution time-wise) to generate the combinations for the $regex - here is one attempt. This needs to be expanded to account for ".." two "anythings" in the pattern. But I think the basic idea is sound, generate a regex pattern dynamically, compile it, and run it against the input dataset.

#!/usr/bin/perl -w
use strict;

my $pattern  = "JEJE";
my @patterns = ($pattern);

for (my $i=0; $i<length($pattern); $i++)
{
   my $copy = $pattern;
   substr ($copy,$i,1) = ".";
   push @patterns, $copy;
}
print join("|",@patterns), "\n";

#prints: JEJE|.EJE|J.JE|JE.E|JEJ.
[download]

I'm not sure that something like this would be faster, might even be slower.. A 'C' implementation like this would be very fast, but in Perl, I am not sure.

for (my $i=0; $i<length($pattern); $i++)
{
   my $saved_char = substr ($pattern,$i,1);
   substr ($pattern,$i,1) = ".";
   push @patterns, $pattern;
   substr ($pattern,$i,1) = $saved_char;
}
[download]