CareerCup

We can use trie to solve this in O(n).

construct trie taking three letter(consecutive) words.
Now after finishing trie, again go thourgh the array in the reverse order and if we find the word in trie print that string.

Here is the code based on the Trie, the code is in java and I am not right now posting the Trie class, you can use any standard Trie implementation available on the net

public void stringProblem (String str)
	{
		Trie tr = new Trie();
		if(str!= null)
		{
			boolean result = false; 
			int len = str.length();
			for(int i = 0; i< len-2;i++)
			{
				String subStr = str.substring(i, i+3);
				tr.insertWord(subStr);
			}
			
			for(int i = len-1;i>1;i--)
			{
				String subStr = str.substring(i-2, i+1);
				StringBuffer sB = new StringBuffer(subStr).reverse();
				if(tr.searchWord(sB.toString()))
				{
					result = true;
					break;
				}
			}
			
			if(result)
				System.out.println("Match Found");
			else
				System.out.println("Match Not Found");

		}
		
	}

/* TestCases
					s.stringProblem("abcdefhhiufedss");
					s.stringProblem("abcdefhhiufdss");
					s.stringProblem("aaa");
					s.stringProblem("aa");
					s.stringProblem("");
					s.stringProblem("ssssssssssssssss");
*/

By using Rabin-Karp algorithm find the hash value for all the 3 letter strings
ex: ABCDEFDCBL

find hash value for ABC - hash it
find hash value for BCD - hash it
find hash value for CDE - hash it
.
.
find hash value for DCB - hash it
find hash value for CBL - hash it
starting from end of the string again find the hash values for all 3 leter strings and check whether the hash is already present in hash table

find hash value for LBC - check if this hash is already present in hash table 1
find hash value for BCD - check if this hash is already present in hash table 1
find hash value for CDF - check if this hash is already present in hash table 1
.
.
find hash value for CBA - check if this hash is already present in hash table 1

time complexicity O(n)
space complexicity O(n)

We can use a bitset of size (26*26*26 - all combinations of 3 letter string). Now parse the string by taking 3 letters at a time and calculate the bit number to be set. As string is abcde; first take abc = (0*26^2 + 1*26^1 + 3*26^0), basically get the value on base 26. set the bit and check the reverse sting also "cba" if this is set, we get the string.

bool find(const char* input,  int len, char out[])
{
  std::set<std::string>> threeletterwords;
  for (int i = 0; i < len; ++i)
  {
     char temp[4] = { input[i], input[i+1], input[i+2], 0};
     char revtemp[4] = { input[i+2], input[i+1], input[i], 0};
     
     if (threeletterwords.find(revtemp) != threeletterwords.end())
     {
         strcpy(out, temp);
         return true;
     }
     
     
     threeletterwords.insert(temp);
   
  }
  
  return false;
}

Hashtable can be used instead of set.

// without DS

bool CheckPolinoms( char* forward, char* reverse )
{
  if( 0x00 == forward || 0x00 == *forward || 0x00 == reverse || 0x00 == *reverse )
  {
    return false;
  }
  bool f = ( *forward++ == *(reverse  ) );
  bool m = ( *forward++ == *(reverse-1) );
  bool l = ( *forward++ == *(reverse-2) );
  return f && m && l;
}

void test17()
{
    char  test[] = "abcdefdcbnp";
    for( size_t i = 0; _countof(test)-2 > i; i++ )
    {
        for( size_t j = _countof(test)-2; 2 < j; j-- )
        {
           if( CheckPolinoms(  &test[i], &test[j] )  )
           {
               cout << i << ", " << j << "\n";
               break;
           }
        }
    }
}

Use suffix tree to get O(n) solution

Suffix Tree is the right answer.

Suffix Tree or Suffix Array is the right answer.

No need of Subfix, just do it in O(n) within one loop :

public static void main(String[] args) 
	{
		String s = "xyzabcddsacba";
		
		HashMap<String, String> map = new HashMap<String, String>();
		
		for(int x = 0; x < (s.length() - 2) ; x++)
		{
			String value = s.charAt(x)+ "" + s.charAt(x + 1) +""+ s.charAt(x + 2) + "";
			String reverse = s.charAt(x + 2)+ "" + s.charAt(x + 1) +""+ s.charAt(x) + "";
						
			if(map.get(value) != null)
			{
				System.out.println(" Result : "+reverse);
				break;
			}
			else{
				map.put(reverse, reverse);
			}
		}		
	}