Найти самый длинный суффикс строки в заданном массиве

Question

Учитывая, что строка и массив строк находят самый длинный суффикс строки в массиве.

, например

струнного = google.com.tr

массив = tr, nic.tr, gov.nic.tr, org.tr, com.tr

возвращает com.tr

Я пытался использовать бинарный поиск с конкретным компаратором, но потерпел неудачу.

C-код был бы рад.

Edit:

Я должен сказать, что им в поисках решения, где я могу сделать столько работы, сколько я могу на стадии подготовки (когда я только массив суффиксов, и я могу сортировать его в каждом путь, построить любую структуру данных вокруг него и т. д.), а не для данной строки найти свой суффикс в этом массиве как можно быстрее. Кроме того, я знаю, что я могу построить trie из этого массива, и, вероятно, это даст мне лучшую производительность, но я очень ленив и держу trie в сыром C в огромном мире запутанного корпоративного кода - это совсем не забавно. Таким образом, подход, подобный бинсону, будет очень приветствуем.

Answer 1

Наивные, псевдо-ответ:

1. Сортировка массива суффиксов по длине (да, может быть строки одинаковой длины, что проблема с задаваемым вопросом я думаю)
2. итерацию над массивом и посмотреть, есть ли суффикс в заданной строке
3. Если это так, выйдите из цикла, потому что все готово! Если нет, продолжайте.

В качестве альтернативы, вы можете пропустить сортировку и просто итерацию, присваивающей biggestString если currentString больше, чем biggestString что совпало.

Edit 0:

Может быть, вы могли бы улучшить это, глядя на массиве, прежде чем руки и рассматривая «минимальные» элементы, которые должны быть проверены.

Например, если .com появляется в 20 участниках, вы можете просто проверить .com против данной строки, чтобы потенциально устранить 20 кандидатов.

Edit 1:

На второй мысли, для того, чтобы сравнить элементы в массиве вам нужно будет использовать сравнение строк. Я чувствую, что любое усиление, которое вы получаете от попытки оптимизировать список строк для сравнения, может быть сведено на нет за счет сравнения их до этого, если это имеет смысл. Был бы признателен, если бы CS-тип меня мог исправить здесь ...

Answer 2

Другой наивный, псевдо-ответ.

Установите логическое значение «found» в false. В то время как «found» is false, итерация по массиву, сравнивающая исходную строку со строками в массиве. Если есть совпадение, установите «found» в true и break. Если нет совпадения, используйте что-то вроде strchr(), чтобы добраться до сегмента строки, следующего за первым периодом.Итерации по массиву снова. Продолжайте, пока не появится совпадение, или пока последний сегмент исходной строки не будет сопоставлен со всеми строками в массиве и не будет соответствовать.

не очень эффективный ....

Answer 3

Предполагая постоянное время адресации символов внутри строк этой проблема изоморфна нахождением наибольшего префикса.

1. i = 0.

2. Пусть S = null

3. Пусть c = prefix[i]

4. Удалить строки a из A если a[i] != c и если A. Заменить S на a, если a.Length == i + 1.

5. Increment i.

6. Перейти к шагу 3.

Это то, что вы ищете?

---

Пример:

Префикс = rt.moc.elgoog

массив = rt.moc, rt.org, rt.cin.vof, rt.cin, к.т.

Pass 0: prefix[0] - 'r' и array[j][0] == 'r' для всех j, поэтому ничего не удаляется из массива. i + 1 -> 0 + 1 -> 1 - наша целевая длина, но ни одна из строк не имеет длины 1, поэтому S остается null.

Пасс 1: prefix[1] - 't' и array[j][1] == 'r' для всех j, поэтому ничего не удаляется из массива. Однако есть строка с длиной 2, поэтому S становится rt.

Пасс 2: prefix[2]: '.' и array[j][2] == '.' для остальных строк, поэтому ничего не меняется.

Pass 3: prefix[3] является 'm' и array[j][3] != 'm' для rt.org, rt.cin.vof и rt.cin так что эти строки будут удалены.

и т.д.

Answer 4

Если массив строк что-то вдоль следующее:

char string[STRINGS][MAX_STRING_LENGTH]; 
string[0]="google.com.tr"; 
string[1]="nic.tr"; 

и т.д., то вы можете просто сделать это:

int x, max = 0; 

for (x = 0; x < STRINGS; x++) { 
    if (strlen(string[x]) > max) { 
     max = strlen(string[x]); 
    } 
} 

x = 0; 

while(true) { 
    if (string[max][x] == ".") { 
     GOTO out; 
    } 
    x++; 
} 

out: 

char output[MAX_STRING_LENGTH]; 
int y = 0; 

while (string[max][x] != NULL) { 
    output[y++] = string[++x]; 
} 

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

Answer 5

Почему вы не используете суффиксные массивы? Он работает, когда у вас есть большое количество суффиксов.

Сложность, O(n(logn)^2), есть версии O(nlogn).

Реализация в c here. Вы также можете попробовать массивы суффикса для Google.