Regular Expression Matching

Problem:
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

 bool isMatch(const char *s, const char *p)
Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

1. If the next character of p is NOT '*', then it must match the current character of s. Continue pattern matching with the next character of both s and p.
2. If the next character of p is '*', then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p... Until we could not match any more characters.

bool isMatch(const char *s, const char *p) {
    assert(s && p);
    if (*p == '\0') return *s == '\0';

    // next char is not '*': must match current character
    if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
    }
    // next char is '*'
    while ((*p == *s) || (*p == '.' && *s != '\0')) {
        if (isMatch(s, p+2)) return true;
        s++;
    }
    return isMatch(s, p+2);
}

Complexity:

time - O(2^n)
space - O(n)

Links and credits:
http://discuss.leetcode.com/questions/175/regular-expression-matching

Optimal solution (that grep, awk, and other tools use):
http://swtch.com/~rsc/regexp/regexp1.html

Find the most frequent non-empty subarray

Problem:
Given an array of ints, find the most frequent non-empty subarray in it. If there are more than one such sub-arrays return the longest one/s.
Note: Two subarrays are equal if they contain identical elements and elements are in the same order.

For example: if input = {4,5,6,8,3,1,4,5,6,3,1}
Result: {4,5,6}

Solution:
The idea is to use a suffix array to easily identify repeated subarrays.

Suffix array is actually a 2D array. The suffix array for the given array {4,5,6,8,3,1,4,5,6,3,1} would be as below. Here, each element of the array itself is an array.

{4,5,6,8,3,1,4,5,6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{8,3,1,4,5,6,3,1}
{3,1,4,5,6,3,1}
{1,4,5,6,3,1}
{4,5,6,3,1}
{5,6,3,1}
{6,3,1}
{3,1}
{1}

After sorting the suffix array, you'd get:
{8,3,1,4,5,6,3,1}
{6,8,3,1,4,5,6,3,1}
{6,3,1}
{5,6,8,3,1,4,5,6,3,1}
{5,6,3,1}
{4,5,6,8,3,1,4,5,6,3,1}
{4,5,6,3,1}
{3,1,4,5,6,3,1}
{3,1}
{1,4,5,6,3,1}
{1}

Checking for matching subarrays is easily done in a suffix array by comparing the prefixes. If you traverse the above sorted array and compare adjacent elements for similarity you'd see the prefix [4,5,6] is occurring maximum number(=2) of times and is also of maximum length. There are other subarrays as well, like [6], [5,6],[3,1] and [1] that are occurring 2 times, but they are shorter than the subarray [4,5,6], which is our required answer.

Complexity:

time - Θ(n) (to construct the suffix array)
space - O(n^2) (might probably avoid making copies of data, and only use indexes to the original array)

Links and credits:
http://www.careercup.com/question?id=20963685
http://en.wikipedia.org/wiki/Suffix_array

Given a string find the largest substring which is palindrome

Problem:
Given a string find the largest substring which is palindrome.

Solution:
Test if a substring is a palindrome starting from its potential "center":

int longestPalindromicSubstring(char* str)
{
 int len = strlen(str);
 int maxLength = 1;
 int start = 0;
 int low, high;
 
 for(int i = 1; i < len; i++)
 {
  // Find longest even length palindrome with
  // center points as i-1 and i
  low = i-1;
  high = i;
  while(low >= 0 && high < len && str[low] == str[high])
  {
   if(high - low + 1 > maxLength)
   {
    start = low;
    maxLength = high - low + 1;
   }
   low--;
   high++;
  }
  
  // Find longest odd length palindrom with
  // center point as i
  low = i-1;
  high = i+1;
  while(low >= 0 && high < len && str[low] == str[high])
  {
   if(high - low + 1 > maxLength)
   {
    start = low;
    maxLength = high - low + 1;
   }
   low--;
   high++;
  }
 }
 
 printf("Longest Palindromic Substring is: ");
 for(int i = start; i <= start + maxLength - 1; i++)
 {
  printf("%c", str[i]);
 }
 
 return maxLength;
}

Complexity:

time - O(n^2)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=20351666
O(n) algorithm (Manacher's Algorithm) is discussed at http://discuss.leetcode.com/questions/178/longest-palindromic-substring