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
Anyone please ?
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.
poor english? it's Russian article
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.
I've just read this article using google translate, it's ok. look at the pictures for more clarity.
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.
why you don't press reply button when you reply someone?
Yes, exactly what is "endpos". Cannot understand through google translate.
This is good paper about Suffix Automata: http://www-igm.univ-mlv.fr/~mac/REC/DOC/B4.ps
Thanks :) I managed to convert this in pdf format. Seems Interesting.let me go through it. Thanks Again :)
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.
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.
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}
Completely understood, thank you very much
have a look at it https://saisumit.wordpress.com/2016/01/26/suffix-automaton/
That helped a lot! Thanks!
glad to know , u enjoyed reading that