KMP.pl


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#!/usr/bin/env perl
use strict;
use warnings;
use 5.016;

chomp(my $str = <>);

my @failure = (0);

my $idx = 0;
for my $start (1..(length($str) - 1)) {
    while (1) {
        if (substr($str, $start, 1) eq substr($str, $idx, 1)) {
            ++$idx;
            last;
        }
        else {
            last if $idx == 0;
            $idx = $failure[$idx - 1];
        }
    }
    push @failure, $idx;
}

say join(' ', @failure);