Find the longest matching prefix in file?

Question

For example, file a.txt:

/abc
/abc/def
/abc/xyz
/abcd
/fghi

Give input and expected results are:

/abc/dog     => /abc
/abc/def12   => /abc/def
/dog         => (NONE)

Is this possible using only shell commands or grep, sed, awk, etc. stuff?

Answer 1

One way to do this is to somewhat reverse the idea of which is the input and use a.txt as the patterns to search for and what you're calling "input" (I'll call "file2") to be what is searched in:

grep -o -f a.txt file2

or

echo "/abc/dog" | grep -o -f a.txt

These won't output anything for "/dog", although the echo version will have a non-zero return code.

Edit:

This will more closely match your requested output:

while read -r line
do
    match=$(echo "$line" | grep -of a.txt)
    match=${match:-(NONE)}
    printf "%-12s => %s\n" "$line" "$match"
done < file2

You can force the search patterns to start at the beginning of the line like this:

grep -o -f <(sed 's/^/^/' a.txt) file2

Answer 2

Sounds like a job for Perl, so here's an awk solution. Minimally tested.

#!/bin/sh
prefixes_file=$1
shift
awk -vprefixes_file="$prefixes_file" '
BEGIN {
    while (getline <prefixes_file) { ++prefixes[$0]; }
}
{
    for (n = length; n >= 0; --n) {
        if (prefixes[substr($0,1,n)]) {
            print $0, "=>", substr($0,1,n);
            break;
        }
    }
    if (n == -1) { print $0, "=>", "(NONE)"; }
}' "$@"

Answer 3

A simple shell script should do the job:

#!/bin/sh

query=$1
file=$2

for i in $(seq 1 ${#query})
do
    current_query=$(echo $query | cut -b1-$i)
    grep -q "$current_query" "$file" || break;
    longest_match=$current_query
done

echo "$longest_match"

You can use it like:

longest_match.sh '/abc/dog' a.txt

and it will print the longest match of the query /abc/dog found in the file a.txt, i.e. /abc/d