CareerCup

a good solution is to create a suffix tree for the given word and then find the deepest internal node in that tree.. the prefix of that particular node will give the longest repeated substring

a brute force approach would be create substrings of different lengths and
search for those substrings. code is

string repeted(string s){
       string ret="";
       for(int i=0;i<s.length();++i)
       for(int j=1;j<s.length();++j){
               string a=s.substr(i,j);  //cout<<a<<"orig"<<endl;
               int k=i+j; // if(k+j<=s.length()) cout<<s.substr(k,j)<<endl;
               while(k+j<=s.length() && s.substr(k,j)==a) k+=j;
               if(ret.length()<k-i-j) ret=s.substr(i,k-i);
               }
               
               return ret;
       
       }

please correct me if im wrong

So how much time was given for complete coding? Bentley's programming pearl book has the simplest implementation (less than 15 lines code) which sort all suffix, and then check common prefix length among adjacent suffix. The time complexity is O(n^2logn) for sorting the suffix (which has avg length of O(n)). Using suffix array this can be done in O(nlogn) though which is bit complex to code. The most efficient method is using suffix tree I guess - which takes even longer to code.

i think a decent solution would be to get all substrings of given string, sort them. Then compare consecutive ones and find the consecutive pair with largest match. The matching part of such a pair ll be longest substring repeated. From the coding perspective this is decent. But is it in terms of memory or computation?? :p

what do you mean by longest repeated string?? the example you gave doesn't make sense for the question you asked. is that longest palindrome in a string? please share more on the example side

if it is the longest palindrome...then start at the middle of the string and go left and right at the same time...each time checking the characters match..when they dont match stop and return the left and right positions indexes and get the string...

excuse me if i understood the question entirely wrong.

Thanks
veeru

str1=rev(str); time 1 min
ans=LCS(str,str1) ; time 4-5 mins(copy from net)
Submit.
toal 7-8 minutes.

No wonder Amazon can't hire people. Asking someone to code this in 5-10 minutes is unreasonable.

I thought a lot but I could not think of anything but a exhausting brute force. But I am not sure they would like this kind of answer. They are looking for something optimum.

Someone plz explain what exactly do we have to find out?

@All :: This question can be done using suffix array ,There is a linear time algorithm for finding all suffixes of a string . Find the suffixes of the suffix recursively will generate all substrings in a string

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{

	int value;
	struct node *child[256];
};

struct trie{
	int count;
	struct node *th;
};

struct node * createNode()
{
	int i;
	struct node *p=(struct node *)malloc(sizeof(struct node));
	p->value = 0;
	for(i=0;i<256;i++)
	{			
		p->child[i] = NULL;
	}
	return p;
}

struct trie * initialize()
{
	struct trie *p = (struct trie *)malloc(sizeof(struct trie));
	p->th = createNode();
	p->count = 0;
	return p;

}

int insert(char *p,struct trie *t)
{

	struct node *h = t->th;
	struct node *q=NULL;
	int level=strlen(p),index,c,i;
	c=0;
	if(!h)return -1;
	for(i=0;i<level;i++)
	{
		index = (int)p[i];
		if(h->child[index] !=NULL)
		{
			if(c==i)
			c++;
		}
		else
		{
			q= createNode();
			h->child[index] = q;
			

		}
		h= h->child[index];
	}
	t->count +=1;
	return c;
}
int getLong(char *p)
{
	int m=-1,c;
	struct trie *t = initialize();
	int i=0;
	while(p[i] !='\0')
	{
		c = insert(p,t);
		p++;
		if(c>m)
			m = c;
	}
	return m;
		
}

int main()
{
	int i,n;
	char p[2500];
	scanf("%s",p);
	printf("\n%d\n",getLong(p));
}

How anana is repeated sub string. In case of banana "ana" is the longest repeatedd substring

Assuming we are trying to compare three DNA sequences. We can first build a suffix tree that encompasses all three sequences. A suffix tree allows all suffices of all sequences to be represented simply by going down from the root (at the top) toward each of the leaves (the ends in the bottom). In the leaves are recorded where that particular suffix came from (e.g., sequences 1, 2 or 3).