Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

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?

share|improve this question
    
I think that the query /abc/dog should return /abc/d. –  mrucci Dec 13 '10 at 20:27
1  
@mrucci: I believe the desired result is that the input should match the entire line in a.txt rather than partial matches. –  Dennis Williamson Dec 13 '10 at 21:18

3 Answers 3

up vote 3 down vote accepted

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
share|improve this answer
    
This needs a.txt to be sorted descending though, but that is easily done using sort -r. –  Arjan Dec 13 '10 at 20:04
    
Oh, and this would also match /dog/abc, unless the patterns in a.txt are prefixed with ^? (Like ^/abc) –  Arjan Dec 13 '10 at 20:15
    
@Arjan: I added a way to anchor the patterns to the beginning of the line. Can you show me an example of sort -r being necessary? –  Dennis Williamson Dec 13 '10 at 21:46
    
Yup, I saw the change but cannot upvote twice ;-). echo "/abc/def12/" | grep -o -f a.txt should yield /abc/def, right? Without sorting it would show /abc. (At least, on a Mac it does.) Maybe it should be sorted by length, not alphabetically, but I guess it has the same effect. –  Arjan Dec 13 '10 at 21:48
    
@Arjan: On my Linux system, echo "/abc/def12/" | grep -o -f a.txt yields /abc/def without sorting. –  Dennis Williamson Dec 13 '10 at 22:19

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)"; }
}' "$@"
share|improve this answer

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

share|improve this answer
    
That could be incredibly slow. –  Dennis Williamson Dec 13 '10 at 21:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.