CareerCup

My suggestion is modified KMP algorithm. This will give solution with O(n) complexity.

namespace KMPForRegularExpressionDFA
{
   class Program
   {
       public static int[] b;
       public static String p;
       public static String t;
       public static int m;
       public static int n;
       static void Main(string[] args)
       {
           p = "aba\\d+a";
           t = "aaaba1aaaaba123111caba123ac";
           b = new int[p.Length + 1];
           m = p.Length;
           n = t.Length;
           KmpPreprocess();
           KmpSearchRegularExp();
           Console.ReadKey();
       }
       public static void KmpPreprocess()
       {
           int i = 0, j = -1;
           b[i] = j;
           while (i < m)
           {
               while (j >= 0 && p[i] != p[j])
               {
                                     j = b[j];
               }
               i++; j++;
               b[i] = j;
           }
       }
       
       public static void KmpSearchRegularExp()
       {
           int i = 0, j = 0;
           while (i < n)
           {
               Boolean flag=false;
               if ((p[j] != '*' && IsThisADigitChar(t[i]) == false) || (p[j] != '*' && IsThisADigitChar(t[i]) == true))
               {
                   flag=true;
               }
               while (j >= 0 && j < m && t[i] != p[j] && flag == true)
               {
                   j = b[j];
               }
               if (j < m && j >= 0 && p[j] == '*' && IsThisADigitChar(t[i]) == true)
               {
                   j++;
                   if (IsThisADigitChar(t[i]) == true)
                   {
                       i++;
                   }
                   if (j < m && j >= 0 && p[j] == '+')
                   {
                       j++;
                       while (IsThisADigitChar(t[i]) == true)
                       {
                                i++;
                       }
                   }
               }
               else
               {
                   i++;
                   j++;
               }
               if (j == m)
               {
                   report(i - j);
                   j = b[j];
               }
           }
private static Boolean IsThisADigitChar(char input)
       {
           if (input >= '0' && input <= '9')
           {


               return true;
           }
           else return false;
       }
//print the string 
Private static void Report(int l)
{
}

       }

You can split the input string based on abcd. check that the length of the array is 3 and 1st and 3rd elements are "". Use the function given on the second element and see if it returns true.

/*
* Slight modification of KMP string searching algorithm
* Time complexity is O(m+n)
* This algorithm takes atmost 2n comparisons
*/

public int[ ] preProcessPattern(char[ ] ptrn) {
int i = 0, j = -1;
int ptrnLen = ptrn.length;
int[] b = new int[ptrnLen + 1];
b[i] = j;
while (i < ptrnLen) {
if(ptrn[i] == '\\' ){ // Ignore \d+ or \d*
i += 3;
}
while (j >= 0 && ptrn[i] != ptrn[j]) {
// if there is mismatch consider next widest border
j = b[j];
}
i++;
j++;
b[i] = j;
}
return b;
}
public boolean searchSubString(char[ ] text, char[ ] ptrn) {
int i = 0, j = 0;
// pattern and text lengths
int ptrnLen = ptrn.length;
int txtLen = text.length;

// initialize new array and preprocess the pattern
int[ ] b = preProcessPattern(ptrn);

while (i < txtLen) {
if(Character.isDigit(text[i])){
if(isMultipleDigit(ptrn, j)){
j+=3;
while(i < txtLen && Character.isDigit(text[i])){
i++;
}
}

if(isSingleDigit(ptrn, j)){
j+=3;
i++;
}
}
while (j >= 0 && text[i] != ptrn[j]) {
j = b[j];
}
i++;
j++;
// a match is found
if (j == ptrnLen) {
return true;
}
}
return false;
}

public boolean isMultipleDigit(char [ ]ptrn, int index){
boolean isMultipleDigit = false;
if(ptrn[index]== '\\' && ptrn[index+1]== 'd' && ptrn[index+2]== '*'){
isMultipleDigit = true;
}
return isMultipleDigit;
}

public boolean isSingleDigit(char [ ]ptrn, int index){
boolean isSingleDigit = false;
if(ptrn[index]== '\\' && ptrn[index+1]== 'd' && ptrn[index+2]== '+'){
isSingleDigit = true;
}
return isSingleDigit;
}

public static void main(String[] args) {
StringSearchingHavingRegexPattern stm = new StringSearchingHavingRegexPattern();

System.out.println(stm.searchSubString("abcd123456abcd".toCharArray(), "abcd\\d*abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd12abcd".toCharArray(), "abc,d\\d*abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd1abcd".toCharArray(), "abcd\\d*abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd123456bcd".toCharArray(), "abcd\\d*abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd1abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd2abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd7abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));

System.out.println(stm.searchSubString("abcd123456abcd".toCharArray(), "abcd\\d+abcd".toCharArray()));
}