The complete list of string based algorithms?

may you please provide the complete list of string based algorithms needed to solve most of string based problems?

algorithms

KMP

boyer more

rabin-karp

aho-corasick

data-structures

suffix array

suffx tree

suffix automaton

trie

some of them can also be solved by dynamic programming like the edit distance problem, number f unique palindromes, etc.

problems

suffix array http://www.codechef.com/tags/problems/suffix-array

suffix tree http://www.codechef.com/tags/problems/suffix-trees

KMP http://www.codechef.com/tags/problems/kmp

aho-corasick http://www.codechef.com/tags/problems/aho-corasick

misc. http://www.codechef.com/tags/problems/string

at codeforces http://codeforces.com/problemset/tags/string%20suffix%20structures?order=BY_SOLVED_DESC

note that some problems can be solved by more than one technique.

i would suggest you to first solve 4- problems of KMP, rabin-karp, aho-corasick, Dynamic programming and only then move on to suffix arrays and suffix trees.

2 Likes

may you also start a thread of problems based on these!

1 Like

just use the problem tags

thank you redd!