algorithm - How is worst case time complexity of constructing suffix tree linear? -

-

i have trouble understanding how worst case time complexity of constructing suffix tree linear - particularly when need build suffix tree string may composed of repeating single character such "aaaaa".

even if construct compressed suffix tree "aaaaa", won't able compress nodes since no 2 edges starting out of node can have string-labels beginning same character.

this result in suffix tree of height 5, , @ each insertion of suffix, need keep traversing root leaf.

here how approached: suffixes: a, aa, aaa, aaaa, aaaaa

create root node, create edge bearing 'a' , connect new node, left bears "$", , repeat process until can aaaaa.

this result in o(n^2) instead of o(n). missing here?

i agree comments, here more details:

the procedure describe forming aaaaa tree o(n), not o(n^2). node , leaf creation constant-time operations, , perform them n==5 times. assumption of o(n^2) seems based on idea you'd traverse root leaf in each step, there no need this; e.g. in ukkonen's algorithm:

  • you keep pointer node left off before inserting next
  • and in case of repetitions don't perform work until repetitions end, , make insertions of final $ mark 1 one, following down characters on edge have created, chain of suffix links in case of more complex repetitions

the key why ukkonen algorithm (details here) o(n) maintains "memory" of make inserts, in form of (a) pointer previous insert made, , (b) network of suffix links. network can vast, there 1 suffix link per internal node, it's still o(n) in size.


Comments

Post a Comment

Popular posts from this blog

python - pip install -U PySide error -

-
does know how avoid following error when running pip install -u pyside per official website instructions here: https://pypi.python.org/pypi/pyside/#installing-pyside-on-a-mac-os-x-system note have done brew install qt successfully. you using pip version 7.0.3, version 7.1.2 available. should consider upgrading via 'pip install --upgrade pip' command. collecting pyside using cached pyside-1.2.4.tar.gz installing collected packages: pyside running setup.py install pyside complete output command /applications/anaconda/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-build-cpxemt/pyside/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-0r7hri-record/install-record.txt --single-version-externally-managed --compile: ...
Read more

arrays - C++ error: a brace-enclosed initializer is not allowed here before ‘{’ token -

-
simple question: i'm trying initialize array within c++ class declaration: using namespace std; #include <string> class myclass{ public: string myarray[] = {"a","b","c"}; }; and i'm getting error: error: brace-enclosed initializer not allowed here before ‘{’ token no, without complied c++11 compiler, cannot initialize member array in declaration. have initialize array member in constructor. , don't use open array if know number of elements initialize array.
Read more

cytoscape.js - How to add nodes to Dagre layout with Cytoscape -

-
i trying add nodes dagre graph through cityscape.js. problem nodes not painted. code have: cy.add({ group: "nodes", data: { id:"n0",name:"n0",weight: 75 }, }); $.ajax(url).done(function(jsontree){ var newnodes=[]; for(var i=1;i<6;i++){ //var child = jsontree.result[i]; newnodes.push( { group: "nodes", data: { id: "n"+i, name:"n"+i}}, { group: "edges", data: { id: "e"+i, source: "n0", target: "n"+i } } ); } cy.add(newnodes); any ideas? have used loaded function reload graph not work. not know if have use specific function reload graph. thank in advance. you need add positions new nodes. cytoscape.js docs : it important note positions of newly added nodes must defined when calling cy.add(). nodes can not placed in graph without valid position — otherwise not displayed. yo...
Read more