определение проблемы не ясно Длинный общий префикс - PullRequest
Новая
       11

определение проблемы не ясно Длинный общий префикс

0 голосов
/ 01 марта 2019

Постановка задачи: В одном из интервью я столкнулся с проблемой кодирования с этим вопросом, которую я не смог понять.

Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)

For example 
s = 'ababac' 
Then substrings are as follow: 
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 

Now, The lengths of LCP of all substrings are as follow 

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 contains only lowercase alphabates.

В этом же вопросе я нашел такой же вопроссообщества, но они являются просто постановкой проблемы, значение которой не может определить. Этот

Одна из проблем с leetcode также в некоторой степени похожа на ту, которую я прекрасно понимаю и кодирую: Самый длинный общий префикс Но мой вопрос звучит так же, но главное отличиеВсе эти типы вопросов предоставляют массив строк, но в моем вопросе есть одна строка, и я должен найти самый длинный общий префикс из этой строки.

Может кто-нибудь, пожалуйста, объясните мне проблему правильно, что именно этот вопрос ищет?

1 Ответ

0 голосов
/ 01 марта 2019

Вам нужно найти самую длинную общую подстроку между двумя строками.В каждом случае один из них - s, исходная строка.Другая строка является правой подстрокой s.Это первый список.

Несколько примеров: 

substring         common   len   reason
s(1, 6) = ababac  ababac    6     Comparing the string with itself yields the entire string
s(3, 6) = abac    aba       3     Only the first 3 characters match
s(4, 6) = bac     -none-    0     The first characters differ, so there is no common prefix.

Помогает ли это?

...