CareerCup

Hash all substrings of length 3. O(n). Look up all reverse substrings of length 3 in this hash set. That part's also O(n).

I think, we can do the following:
1)Take every substring of length 3;
2)Reverse it.
3)Use KMP to check if it is present in the string.

Note: For KMP, we can compute the Failure Function just once and use that everytime.

Let extend it to length of k:

All sub strings of length k are (n-k+1).
Now checking for each substring that weather substring of length k exists or not in this string using KMP can be done in O(n).

So complexity will come out as O(n^2)


But I think suffix trie can be one of best approach as it can be done O(n(log(k))) using that.

public int findReverse(String inputString, int numChars){
        if(inputString == null || inputString.length() < numChars){
            return -1;
        }else{
            ArrayList<String> list = new ArrayList<String>(inputString.length()/numChars);
            for(int i=0; i < inputString.length() && inputString.length() > i+numChars; i = i + numChars)  {
                list.add(inputString.substring(i, numChars+i));
            }
            for(String temp: list){
                temp = reverseStr(temp);
                if(inputString.indexOf(temp) != -1)
                    return 1;
            }
        }
        return -1;
    }

Use suffix tree.

Do the following:

1. Reverse the string
2. Find the common sequences using modified (LCS).
3. Print only those common sequences which are of length 3.

eg. abcdefgcbaktfed

rev: deftkabcgfedcba

common: abc, def, ab, ba, ed ...

print only : abc, def (length : 3)

for abcdcba,dcb is also a reverse of bcd.

WE can try a simpler approach rather following the famous algorithms .
It need O(n^2) time complexity though.

all we need to do is to perform a modified palindrome checking.

consider the string "ABCDEFGHDCBAIJK"



maxlength=0;
have two positions start and end. 
for  i=0 to A.length-1  
{
  start=i;
  end=A.length();
 length=0;
  if(A[start]==A[end]) 
   {
     while(A[start]==A[end] && start <=end)
      {
        increment length;
        start++; 
        end--;
      }
     if(maxlength<length)
      {
        maxlength=length;
        // mark positions of the array.
      }
   }
}

public static List<String> subStringInReverse(char[] charArray, int subStringSize)
{
List<String> reversedSubString = new ArrayList<String>();
if(subStringSize == 0)
{
reversedSubString.add("Sub string size fetch should be greater than 0");
return reversedSubString;
}

if(charArray.length - 1 < subStringSize)
{
reversedSubString.add("Sub String size should be less than or equal to size of the string");
return reversedSubString;
}

for(int i = 0, j = charArray.length - 1; i < j; i++, j--)
{
if(charArray[i] == charArray[j])
{
int count = 1;
while(count < subStringSize)
{
if(charArray[i + count] == charArray[j - count])
{
count++;
continue;
}

break;
}

if(count == subStringSize) {
int offset = j - ( subStringSize - 1 );
reversedSubString.add(String.copyValueOf(charArray, offset , subStringSize));
}
}
}

if(!reversedSubString.isEmpty())
{
reversedSubString.add(0, "Sub String found is : ");
return reversedSubString;
}

reversedSubString.add("Sub string doesn't exist");
return reversedSubString;
}

<pre lang="" line="1" title="CodeMonkey22227" class="run-this">public class StrRpt {
public static void main(String[] z) {
String s = "abcdcba";
for (int j = s.length(); j >= 0; j--) {
for (int i = 0, end = i + j; i < s.length() && end < s.length(); i++, end++) {
String sub = new StringBuffer(s.substring(i, end)).reverse()
.toString();
if (s.contains(sub)) {
System.out.println(s.substring(i, end));

}
}
}
}
}
</pre><pre title="CodeMonkey22227" input="yes">
</pre>

General method:
create a prefix tree with the given string O(len of string) and then find prefixes on the reverse string (here of len 3) and then apply it on the prefix tree created earlier to find any match.If you find any match for a certain length(not necessary for whole string) then that string would be the solution ie the string which is present in reverse as well in the given string

total complexity: o(len of string) + o(len of matched string) = O(len of string)


ex- if the given string is abcdcbad then the prefix tree would be sth like:

............................................................
.           .                     .                        .
.           .                     .                        .
.           b............         c............           d$....... 
.           .           .         .          .             .      .
abcdcbad$   cdcbad$     ad$       dcbad$     bad$          cbad$  bad$

and the prefixes from the reverse of the string would be:
dabcdcba
abcdcba
bcdcba
cdcba
dcba
cba
ba
a

now apply one string at a time on the prefix tree and the string abcdcba would match as a whole the means that abcbcba would be a reverse string in the given string....

similarly the string "dcba" in the above prefix of the reverse string it matches so abcd/dcba is also a solution.

total complexity: build prefix tree: O(len of string) +
find the prefix in the prefix tree i.e. O(len of string to find * no of prefix)
= o(n) + o(3 * n) = o(n)
note: here len of string to find=3 in general it could be n.

Modifying code provided by noone on November 26, 2011

We can get a successful solution as given in following code.
------------------------------------------------------


class a
{
public static void main(String[] args) {
String s="dsafghabbdchgfa";

for(int i=0;i<s.length()-3;i++){

StringBuffer sb = new StringBuffer(s.substring(i,i+3));
String s1=sb.reverse().toString();
if(s.contains(s1))
{
System.out.println(s1);
}
else
System.out.println("not found");
}
}
}

<pre lang="" line="1" title="CodeMonkey22011" class="run-this">class a
{
public static void main(String[] args) {
String s="dsafghabbdchgfa";

for(int i=0;i<s.length()-3;i++){

StringBuffer sb = new StringBuffer(s.substring(i,i+3));
String s1=sb.reverse().toString();
if(s.contains(s1))
{
System.out.println(s1);
}
else
System.out.println("not found");
}
}
}
</pre><pre title="CodeMonkey22011" input="yes">
</pre>

Solution 1:
1. Reverse the array.
2. get strings of length 3. --> n-3
3. for each of those strings search whether it present in the main string

O(n2)
Solution 2:
number a to z as 1 to 26
1. take one more int array of size n-2 to store sums.
2. store all the sums in that array.
3. search for same sums and compare them

O(nlogn)

Dear all,
Please my code
void string_rev_check(char *str,char *target)
{
int len=strlen(target)-1;
int hash[255]={0,};
int flag=-1;
for(int i=0;str[i]!='\0';i++)
{
hash[str[i]]++;
}
for(int i=len;i>=0;i--)
{
if(hash[target[i]]==1)
{
continue;
flag=1;
}
else
{
cout<<endl<<"sequence not there";
return ;
}
}
if(flag==1)
cout<<endl<<"sequence is there";
}

#include<iostream>
#include<map>
#include<iterator>
using namespace std;

void Sub( string s )
{
map<string , int> m;
map<string,int>::iterator it;
        int start = 0;
        int end = start+2;
        while( end <= s.length()-1 )
        {

        string a;
        string b;
                for( int i=start ; i<=end ; i++ )
                {
                        a = a+s[i];
                }
                for(int i=end ; i>=start ; i--)
                {
                        b = b+s[i];
                }
                m[a]++;
                m[b]++;
                if( m[a] >= 2 )
                        cout << a << endl;
                start++;
                end++;
        }


}


int main()
{
Sub("abcdcba");

return 0;

}
~

step 1: Make a suffix trie of the string complexity O(n)
step 2 reverse the string no extra complexity can be reversed along with step 1
step 3: check the reversed string with with trie

This is about 2n

def reversedSubStringExists(s, l): 
    forward = []
    for i in range(0, len(s) - (l - 1), 1): 
        forward.append(s[i:i+l])

    for i in range(len(s) - 1, l - 2, -1):
        substr = ''
        for j in range(l):
            substr = substr + s[i - j]
        if substr in forward:
            return substr 
    return ''
s = "bananas"
print "in string", s, "reversed sub string found is", reversedSubStringExists(s, 4)

public static boolean isContainRevSubstring(String str){

ArrayList<String> list = new ArrayList<String>();
for(int i = 0 ; i <= str.length() - 3 ; i++){

String temp = str.substring(i, i+3);
list.add(temp);

}

for(int i = 0 ; i < list.size() ; i++){
StringBuffer temp = new StringBuffer(list.get(i));
if(list.contains(temp.reverse().toString())){
return true;
}
}

return false;

}

Las-Vegas Rabin karp method : O(N) simple to code. 
     Use suffix array of S + # + rev(S) and find if the lcp of a suffix is >=3 

     void rabin_karp(string& text)
     {
              unordered_map<long long, int> hm;
              int n = text.size(), m = 3;
              for (int i=0; i < 3; i++)
                   hp = int_mod(hp*B + text[i], M);
              for (int i=0; i <= n-3; i++) 
              {
                      hm.insert(make_pair(hp, i));
                      if (i + 3 < n)
                      {
                               hp = int_mod(hp - int_mod(text[i]*E, M), M);
                               hp = int_mod(hp*B, M);
                               hp = int_mod(hp + text[i+m], M);
                      }
              }   
              hp  = 0;
              for (int i=0; i < 3; i++)
                          hp = int_mod(hp*B + text[n-1-i], M);
              string str = revese_copy(text.begin(),text.end());
              for (int i=0; i <= n-3; i++)      
              {
                          auto same_hash = hm.equal_range(hp);
                          for (auto it = same_hash.first; it != same_hash.second; it++)
                          {} // check for if substring matchs // las-vegas version
                           if (i + m < n)
                           {
                                       hp = int_mod(hp - int_mod(E*text[n-1-i], M), M);
                                       hp = int_mod(hp*B, M);
                                       hp = int_mod(hp*text[n-1-(i+m)], M);
                           }
                }
              }
     }

public class StringComparision {

public static String reverse(String s) {
StringBuffer sb = new StringBuffer(s);
return sb.reverse().toString();

}

public static String findCombination(String str) {
for (int i = 0; i < str.length(); i++) {
String subString = str.substring(i, i+3);
String rev = reverse(subString);
if (str.contains(rev)) {
return rev;
}
}
return "Not Found";
}

public static void main(String[] args) {
String str = "qwertyabcasdfgcba";
System.out.println(findCombination(str));

}

}

Algorithm as suggested by eugene
1.Create hashmap and put all substrings of size 3 in it
2. reverse string
3. for each substring of reversed string, print all entries that are already present in hashmap

import java.util.HashMap;

class TreeClass {

	public static void main(String Args[]) {
		String text = "qwertyabcasdfgcba";
		int length = 0;

		HashMap<String, Integer> map = new HashMap<String, Integer>();

		while (length < text.length() - 2) {
			String tmp = text.substring(length, length + 3);

			if (map.containsKey(tmp)) {
				int val = map.get(tmp);
				val++;
				map.put(tmp, val);
			} else
				map.put(tmp, 1);

			length++;

		}

		String rev = "";
		length = text.length() - 1;
		while (length >= 0) {
			rev = rev.concat(Character.toString(text.charAt(length)));
			length--;
		}

		length = 0;
		while (length < rev.length() - 2) {
			String tmp = rev.substring(length, length + 3);

			if (map.containsKey(tmp)) {
				System.out.println(tmp);
			}

			length++;
		}

	}
}