Sunday, August 23, 2015

String functions review

August 23, 2015


1. stringDemo.cpp

Including
atoi 5 versions of implementation


2. Scramble string:



3. strstr

Boyer-Moore algorithm

Read the string function website and get ideas:

http://algs4.cs.princeton.edu/53substring/

http://zjalgorithm.blogspot.ca/2014/12/leetcode-in-java-implement-strstr.html

Need a test case to help me figure out Boyer-Moore algorithm again on August 23, 2015.
Here is a short one for me to memorize the idea:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore.htm

read the article quickly in 20 minutes on August 23, 2015
http://web.cs.ucdavis.edu/~gusfield/cs224f11/bnotes.pdf

Dec. 12, 2015 video watch:
https://www.youtube.com/watch?v=fHNmRkzxHWs
one of examples the presenter gave in his Cpp conference video.
Know that there is a definitely better algorithm than O(n^2), but also, need to know what the ideas are to beat the naive solution. 

Dec. 11, 2015
Need to work on a small test case, therefore, the algorithm can be easily recalled, and ideas of algorithms can be demoed clearly in the example. Go to find my favorite string, substring. (January 5, 2015, read the wiki page, https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, read 'The bad character rule' and 'The good suffix rule' )

4. longest palindromic string

5. Look up standard string function implementation, quick review and learn:


January 5, 2016
Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm. 

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html



No comments:

Post a Comment