psan's blog

Suffix Automation
By psan, 11 years ago, In English

Hi all,I want to learn Suffix Automation.I have seen this is very powerful tool for string problems.I searched a lot on internet but could not able to get somthing worth.I have tried emaxx.ru but not able to get that article.

could anyone consider my request and guide me from here. Thanks

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Anyone please ?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks :) but i was reading this article.i was not unable to understand this article due to poor english.any other source i am looking for.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah,I have translated this page from google translate.after reading tranlating page i am not getting thier sentences properly. I hope you will also find this issue.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've just read this article using google translate, it's ok. look at the pictures for more clarity.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Okay,That may be true.I understand figures.I am not getting concept of endpoints. If you understand that could you pls explain some key points of algorithm here.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is good paper about Suffix Automata: http://www-igm.univ-mlv.fr/~mac/REC/DOC/B4.ps

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks :) I managed to convert this in pdf format. Seems Interesting.let me go through it. Thanks Again :)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I think one of the original papers is this one: "The Smallest Automation Recognizing the Subwords of a Text", or at least I find this paper quite elaborate and readable.

It should be easily google-able with the title above.

edit: The link provided by 1Codeforces is also very great.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am also learning about this, and am reading the article on emaxx. I, however, find the concept 'endpos' very confusing. Could someone please clarify it for me by restating the definition which might be spoiled by google translate, and giving me an example. Thank you.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Let t be substring of s. Then endpos(t) = {x: s.substr(x - t.length(), t.length()) = t}. I.e. it is the set of positions. For example s = abacaba:

    endpos("a") = {0, 2, 4, 6}, 

    endpos("ab") = {1, 5}, 

    endpos("abac") = endpos("bac") = endpos("ac") = endpos("c") = {3}

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

have a look at it https://saisumit.wordpress.com/2016/01/26/suffix-automaton/

→ Reply