If pattern and number of allowed substitutions are small, you can simply throw a regex at it:

use strict;
use warnings;
use 5.010;
my $pattern = "JEJE";
my $string = "EJKJUJHJDJEJEJEDEJOJOJJJAHJHJSHJEFEJUJEJUJKIJS";
my @parts = qw/
    JE.. J..E ..JE 
    J.J. .E.E .EJ.
    /;
my $regex = join '|', @parts;

while ($string =~ /($regex)/g) {
    say "$1 at position ", pos($string);
}
__END__
JKJU at position 5
JHJD at position 9
JEJE at position 13
JEDE at position 17
JOJO at position 21
JJJA at position 25
JHJS at position 30
JEFE at position 35
JUJE at position 39
JUJK at position 43
[download]

If you also want overlapping matches, use while ($string =~ /(?=($regex))./g) { ... }