Наибольшая длина общего префикса из всех подстрок и строки - PullRequest
Новая
       42

Наибольшая длина общего префикса из всех подстрок и строки

0 голосов
/ 01 декабря 2018

Я нашел похожие вопросы в StackOverflow, но у меня другой вопрос.

Учитывая, что строка s содержит строчные буквы alphabet.Я хочу найти длину Longest common Prefix всех подстрок.

Например, 

s = 'ababac'

Тогда подстроки выглядят следующим образом: 

1: s(1, 6) = ababac
2: s(2, 6) = babac
3: s(3, 6) = abac
4: s(4, 6) = bac
5: s(5, 6) = ac
6: s(6, 6) = c

Теперь, длины LCP всех подстрок следующие: 

1: len(LCP(s(1, 6), s)) = 6 
2: len(LCP(s(2, 6), s)) = 0
3: len(LCP(s(3, 6), s)) = 3
4: len(LCP(s(4, 6), s)) = 0
5: len(LCP(s(5, 6), s)) = 1
6: len(LCP(s(6, 6), s)) = 0

Я использую символьное сопоставление 

    string commonPrefix(string s1, string s2) { 
        int minlen = minlength1(s1, s2); 
        char current; 
        int result = 0;
        for (int i=0; i<minlen; i++) { 
            current = s1[i]; 
            for (int j=1 ; j<n; j++) 
                if (s2[i] != current) 
                return result; 
            result++;
        } 

        return result; 
    }

Но все же это O (n2).Я знаю, что все подстроки накладываются друг на друга, это можно оптимизировать дальше.Кто-нибудь может помочь оптимизировать этот код?

...