Найти Num перекрывающихся и не перекрывающихся подстроки в струнной

Question

PS: Это не дубликат How to find the overlap between 2 sequences, and return it

[Хотя я прошу решений в выше подхода, если он может быть применен к следующей задаче]

Q: Несмотря на то, что я правильно понял, он по-прежнему не является масштабируемым решением и определенно не оптимизирован (низкий балл). Прочтите следующее описание проблемы и предложите лучшее решение.

Вопрос:

Для простоты, мы требуем префиксы и суффиксы, чтобы быть непустым и короче всей строки S. Граница строки S является любая строка, которая является как префикс и суффикс. Например, "cut" является границей строки "cutletcut", а строка "barbararhubarb" имеет две границы: "b" и "barb".

class Solution { public int solution(String S); } 

, что, учитывая строку S, состоящая из N символов, возвращает длину самой длинной границы, которая имеет по крайней мере три неперекрывающихся вхождений в данной строке. Если нет такой границы в S, функция должна возвращать 0.

Например,

• если S = "barbararhubarb" функция должна возвращать 1, как описано выше;
• , если S = "ababab" функция должна возвращать 2, так как "ab" и "abab" оба границы S, но только "ab" имеет три неперекрывающихся вхождений;
• если S = "baaab" функция должна вернуть 0, так как ее единственная граница "b" происходит только дважды.

Предположим, что:

• N представляет собой целое число в диапазоне [0..1,000,000];
• строка S состоит только из прописных букв (a−z).

Сложность:

• ожидается в худшем случае сложность O(N);
• ожидаемая наихудшая сложность пространства - O(N) (не считая хранения, необходимого для входных аргументов).

def solution(S): 
    S = S.lower() 
    presuf = [] 
    f = l = str() 
    rank = [] 
    wordlen = len(S) 
    for i, j in enumerate(S): 
     y = -i-1 
     f += S[i] 
     l = S[y] + l 
     if f==l and f != S: 
      #print f,l 
      new=S[i+1:-i-1] 
      mindex = new.find(f) 
      if mindex != -1: 
       mid = f #new[mindex] 
       #print mid 
      else: 
       mid = None 
      presuf.append((f,mid,l,(i,y))) 
    #print presuf 
    for i,j,k,o in presuf: 
     if o[0]<wordlen+o[-1]: #non overlapping 
      if i==j: 
       rank.append(len(i)) 
      else: 
       rank.append(0) 
    if len(rank)==0: 
     return 0 
    else: 
     return max(rank) 

Мои решения Время сложность: O (N 2) или O (N 4) Помощь высоко оценили.

Answer 1

У меня есть (Java) решение, которое выполняет O (N) или O (N ** 3), для итогового 90/100 в целом, но я не могу понять, как это сделать, хотя 2 разных тестовых корпуса :

почти_all_same_letters aaaaa ... aa ?? aaaa ?? .... aaaaaaa 2.150 s. ОШИБКА ВРЕМЕНИ время работы:> 2,15 с, ограничение по времени: 1,20 сек.

same_letters_on_both_ends 2.120 s. TIMEOUT ERROR время работы:> 2.12 сек., Ограничение по времени: 1,24 сек.

Редактировать: Прибито! Теперь у меня есть решение, которое выполняется в O (N) и передает все проверки для результата 100/100 :) Я не знал Codility, но это отличный инструмент!

Answer 2

У меня есть решение с массивами суффикса (на самом деле существует алгоритм для построения SA и LCP в линейном времени или что-то еще хуже, но, конечно, не квадратичное).

Все еще не уверен, что я могу обойтись без RMQ (O (log n) с SegmentTree), который я не мог передать своим собственным делам и кажется довольно сложным, но с RMQ он может (не упоминать подход с for loop вместо RMQ, что сделало бы его квадратичным в любом случае).

Решение выполняется довольно быстро и проходит мимо моих 21 тестового чехла с различными льготами, которые мне удалось создать, но все еще не удалось выполнить некоторые из них. Не уверен, что это помогло вам или дало вам представление о том, как подойти к проблеме, но я уверен, что наивное решение, как сказал @Vicenco в некоторых своих комментариях, не может стать лучше, чем Silver.

EDIT: удалось исправить все проблемы, но все равно замедлить работу. Я должен был обеспечить соблюдение некоторых условий, но мне пришлось усложнять эту задачу, но я не уверен, как ее оптимизировать. Будет держать вас в курсе. Удачи!

Answer 3

Мое решение - комбинация алгоритмов Рабина-Карпа и Кнута-Морриса-Пратта. http://codility.com/cert/view/certB6J4FV-W89WX4ZABTDRVAG6/details

Answer 4

protected int calcBorder(String input) { 
    if (null != input) { 
     int mean = (input.length()/3); 
     while (mean >= 1) { 
      if (input.substring(0, mean).equals(
        input.substring(input.length() - mean))) { 
       String reference = input.substring(0, mean); 
       String temp = input 
         .substring(mean, (input.length() - mean)); 
       int startIndex = 0; 
       int endIndex = mean; 
       int count = 2; 
       while (endIndex <= temp.length()) { 
        if (reference.equals(temp.substring(startIndex, 
          endIndex))) { 
         count++; 
         if (count >= 3) { 
          return reference.length(); 
         } 
        } 
        startIndex++; 
        endIndex++; 
       } 
      } 
      mean--; 
     } 
    } 
    return 0; 
} 

Answer 5

The Z-Algorithm будет хорошим решением.