CareerCup

I think I myself have a solution.
Suppose we have to search the phrase "This is".
Then for every occurrence of "This" we will have a node in the trie with the index stored
Then we search for the word "is" in the trie, and hence we can find all the indices in which "is" occur in the large text
Then for each index at which "is" occurs, we can check in O(m+n) time { all the indices at which index of occurrence of "is" - length of("the ") } which matches with the indices at which "the" occurs.
where m,n- number of indices at which "the" , "is" occur respectively.
This approach can be extended to phrases with more than two words in this manner-
For e.g.- we have to search "This is a good approach"
We keep all the indices at which "This is" occurred in a set say S. Then we match all indices at which "a" occurs and match it in the above mentioned manner for all the indices in S and continue so on

The key here is that for non reduce-able fraction the gcd(greatest common divisor) of the numerator and denominator must be 1 or in other words they must be co-prime.

int gcd(int a,int b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}
bool isNonReduceableFraction(int numerator,int denominator){
	if(gcd(numerator,denominator)==1)
		return true;
	return false;
}

#include<bits/stdc++.h>
using namespace std;
int romanToInt(string s){
	int res=0;
	for(int i=0;i<s.length();++i){
		if(s[i]=='L')
			res+=50;
		else if(s[i]=='X'){
			if(i<s.length()-1 && (s[i+1]=='L') )
				res-=10;
			else
				res+=10;
		}
		else if(s[i]=='V')
				res+=5;
		else if(s[i]=='I'){
			if(i<s.length()-1 && (s[i+1]=='X' || s[i+1]=='V') )
				res--;
			else
				res++;
		}
	}
	return res;
}
bool comp(string a,string b){
	istringstream isA(a);
	istringstream isB(b);
	string splitStringA[2],splitStringB[2];
	string temp;
	int i=0;
	while(isA>>temp)
		splitStringA[i++]=temp;
	i=0;
	while(isB>>temp)
		splitStringB[i++]=temp;
	if(splitStringA[0]<splitStringB[0])
		return true;
	else if(splitStringA[0]>splitStringB[0])
		return false;
	else
		return romanToInt(splitStringA[1])<=romanToInt(splitStringB[1]);
}
int main(){
	string names[6]={"Richard V","Henry VI","Edward II","Richard XXV","Henry IX","Edward LII"};
	sort(names,names+6,comp);
	for(int i=0;i<6;++i)
		cout<<names[i]<<endl;
return 0;
}

i think a slight modification of the binary search can be used for this purpose in which each time we check if (num>=arr[low])&&(num<=arr[mid]){ high=mid} and so on