By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
431,816 Members | 1,332 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 431,816 IT Pros & Developers. It's quick & easy.

Find out the Longest Common Prefix in an array of alphabets,No prefix is given.

P: 2
You are given a sequence of lower case alphabetical characters as
input, say A[0], ..., A[N-1]. N will be at most 100.

A prefix of the sequence is some initial segment of the string - that
is, A[0], ..., A[K-1], for some integer K, 1 <= K <= N.

You have to output the longest prefix which occurs multiple times in
the string.

If no prefix occurs again, you must output "NO". (without quotes)

For example, if the input string is "ababaa", then the possible
prefixes are {"a", "ab", "aba", "abab", "ababa", "ababaa"}. We can see
that "a" occurs at indices 2, 4, and 5. The string "ab" occurs again in
position 2. "aba" occurs in position 2. "abab" does not occur again in
the string. So the longest prefix that occurs multiple times in the
string is "aba".
2 Weeks Ago #1
Share this Question
Share on Google+
3 Replies


100+
P: 103
Follow the posting guidelines and make changes to the post by mentioning your progress and code and what you've tried so far to solve this question.
2 Weeks Ago #2

P: 2
Expand|Select|Wrap|Line Numbers
  1. #include<stdio.h>
  2. void main()
  3. {
  4. int i;
  5. char arr[100];
  6. for(i=0;i<100;i++)
  7. scanf("%d",&arr[i]);
//I dont understand the logic of how to check the prefixes without having a fixed pattern otherwise i would have done KMP PATTERN SEARCH please help!!
2 Weeks Ago #3

100+
P: 103
For I/P "ababaa",

prefixes : {"a", "ab", "aba", "abab", "ababa", "ababaa"}

Let's call them substrings.

Logic to get these substrings:
Expand|Select|Wrap|Line Numbers
  1. ...
  2. //str = "ababaa"
  3. //i=0 initially
  4. while(i<strlen(str)){
  5.   temp[i]=str[i];
  6.   temp[i+1]='\0';
  7.   ....
  8.   ....
  9.   i++;
  10. }
  11. ...
  12.  
The values of temp on different iterations would be: "a", "ab", "aba", "abab", "ababa", "ababaa"

Now the logic for the number of occurrences of a substring in a string can be used with each iteration of the loop. Once these values are known, we can determine the longest substring that occurred multiple times with the help of global variables such as maxSubStr (char array) and maxSubStrCount (int, initially 0). Like:

Expand|Select|Wrap|Line Numbers
  1. if (currentSubStrCount > maxSubStrCount) {
  2.   maxSubStrCount = currentSubStrCount ;
  3.   strcpy(maxSubStr, currentSubStr);
  4. }
The actual implementation may differ based on the approach. In the end, you can output the values of maxSubStrCount and maxSubStr.

" If no prefix occurs again, you must output "NO" "
You can use a flag variable to cover this case.
2 Weeks Ago #4

Post your reply

Sign in to post your reply or Sign up for a free account.