Самый быстрый метод определения всех подстрок существующей строки - PullRequest
Новая
       17

Самый быстрый метод определения всех подстрок существующей строки

2 голосов
/ 20 марта 2012

Допустим, у меня есть строка "Hey".Я хотел бы определить все комбинации символов, которые существуют в этой строке, как fast , насколько это возможно.Результирующий алгоритм должен сгенерировать это: 

H, e, y, He, ey, Hey

Алгоритм должен не генерировать строку "Hy", потому что не существует в строке в качестве подстроки.

Ответы [ 2 ]

3 голосов
/ 20 марта 2012

Существует O(n^2) этих подстрок длиной [1,n], поэтому любой алгоритм для генерации всех их будет O(n^2) * O(n) = O(n^3):

(*) См. Edit2 в конце - в зависимости от реализации строки - сложность может варьироваться от O(n^2) до O(n^3)

Псевдокод: 

result <- {} #result is a set if dupes should be terminated, otherwise - it is a multiset.
for i from 0 to s.length:
   for j from i+1 to s.length:
      result.add(s.substring(i,j))
return result

Обратите внимание, что вы можете сделать «обман», создав итератор и сгенерировав подстроки на лету, это должно выглядеть примерно так [псевдокод]: 

class MyIterator:
  String s
  int i,j
  MyIterator(String s):
     this.s = s
     i = 0
     j = 0
  next():
     j = j + 1
     if (j >= s.length):
     i = i + 1
     j = i + 1
     if (i >= s.length): 
         throw exception
     return s.substring(i,j)

Обратите внимание, что создание итератора - это O(1), а каждая итерация - O(n) - но для создания всех элементов вам нужно O(n^2) шагов, поэтому сложность в целом остается O(n^3), но вы уменьшаете задержку ваше заявление.

EDIT:
Я отредактировал сложность, утверждая, что это O(n^2), это неправильно, сложность составляет O(n^3), так как вам нужно генерировать строки переменной длины, некоторые из них длинные. По крайней мере половина сгенерированных подстрок будет иметь длину n/2 - таким образом, общая сложность составляет Theta(n^3)

EDIT2:
В некоторых случаях это может быть O(n^2) - в зависимости от реализации строки. Например, в java - он использует один char[] и «играет» только с offset и length - поэтому в java - создание на самом деле O(n^2), поскольку создание подстроки O(1)
Однако в C - это O(n^3), так как каждая подстрока должна быть скопирована в другой char[].

0 голосов
/ 20 марта 2012

Проверьте реализацию n-грамм в php.

В вашем примере строка: Hey

H, E, Y - униграммы

HE, EY - биграммы

ЭЙ - триграмма

...