Not And or Or, but Xor (^):

use strict;
use warnings;

my $str1 = '//depot/Efp/Celox/CELOX-3.5.0/CeloxStart.sln';
my $str2 = '//depot/Efp/Celox/MAIN/CeloxStart.sln';
my $str1r = $str1;
my $str2r = $str2;

# Find and strip common prefix
my $match = ($str1 ^ $str2) =~ /^(\x00*)/;
substr $str1r, 0, $+[1], '' if $match;
substr $str2r, 0, $+[1], '' if $match;

# Find and strip common suffix
$match = (reverse ($str1) ^ reverse ($str2)) =~ /^(\x00*)/;
substr $str1r, -$+[1], length ($str1r), '' if $match;
substr $str2r, -$+[1], length ($str2r), '' if $match;

print "$str1r\n$str2r\n";
[download]

Prints:

CELOX-3.5.0
MAIN
[download]

Update: process both strings