Как найти одинаковые части в массиве строк?

Вообще, исходя из вашего задания и данных, вы должны получить общий префикс astra-srv:658712 - потому что только эта строка является общей для всех строк. Но, допустим, мы хотим получить префиксы, которые состоят из минимум 2 секций.

Ваша задача это типичный поиск префиксов, решается префиксным деревом (или в простонародье trie)

Смысл алгоритма в том, чтобы при исходных данных

astra-srv:658712/sys/broker/state/astra-srv:658712_svc_core
astra-srv:658712/sys/broker/state/astra-srv:658712_svc_client_notify
astra-srv:658712/sys/broker/state/astra-srv:658712_svc_mailer
astra-srv:658712/svc

Каждую строчку разделить по слешу / и построить дерево типа такого

astra-srv:658712
    sys
        broker
            state
                astra-srv:658712_svc_core
                astra-srv:658712_svc_client_notify
                astra-srv:658712_svc_mailer
    svc

отсюда видно, что нужные вам узлы, либо имеют более одного потомка как state, либо не имет потомков, как svc. По хорошему astra-srv:658712 имеет два потомка, то есть это самый общий префикс, но раз мы договорились, что префикс как минимум должет включать 2 секции, то мы проигнирируем astra-srv:658712

Теперь к коду. Нам надо определить узел префиксного дерева и методы для добавления туда строки и для извлечения общих префиксов. Методы простые как топор, потому не комментирую

class TrieNode
{
    private Dictionary<string, TrieNode> childen = new Dictionary<string, TrieNode>();

    public void Add(string[] data, int index = 0)
    {
        if (index >= data.Length) return;
        var item = data[index];
        if (!childen.ContainsKey(item)) childen.Add(item, new TrieNode());
        childen[item].Add(data, index + 1);
    }

    public void CollectSimilarPaths(List<string> currentPath, List<String> result)
    {
        if (currentPath.Count > 1 && (childen.Count == 0 || childen.Count > 1))
        {
            result.Add(string.Join("/", currentPath));
            return;
        }

        foreach (var kv in childen)
        {
            currentPath.Add(kv.Key);
            kv.Value.CollectSimilarPaths(currentPath, result);
            currentPath.RemoveAt(currentPath.Count - 1);
        }
    }
}

Чтобы воспользоваться этой структорой, определим данные в строках

var data = new[] {
    "astra-srv:658712/sys/broker/state/astra-srv:658712_svc_core",
    "astra-srv:658712/sys/broker/state/astra-srv:658712_svc_client_notify",
    "astra-srv:658712/sys/broker/state/astra-srv:658712_svc_mailer",
    "astra-srv:658712/svc"
};

Корень дерева

var root = new TrieNode();

Закидываем в дерево строки, предварительно порубив из по /

foreach (var line in data)
    root.Add(line.Split("/"));

Извлекаем похожие префиксы длиной более 1

var similar = new List<string>();
root.CollectSimilarPaths(new List<string>(), similar);

Вывод на печать

foreach (var line in similar)
    Console.WriteLine(line);

В консоли видим

astra-srv:658712/sys/broker/state
astra-srv:658712/svc