1. Find the substring in a string.

Solution

O(m*n) can be done [m is substring and n is string].

Better one is Knuth-Morris-Pratt algorithm.

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

2. Find the longest palindrome in the string.

O(N*N) can be found.

For each index in the string, traverse in both directions as palindrome keeps building.

http://articles.leetcode.com/longest-palindromic-substring-part-I/

string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l–;
r++;
}
return s.substr(l+1, r-l-1);
}

string longestPalindromeSimple(string s) {
int n = s.length();
if (n == 0) return “”;
string longest = s.substr(0, 1);  // a single char itself is a palindrome
for (int i = 0; i < n-1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;

string p2 = expandAroundCenter(s, i, i+1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}