Thursday, September 6, 2012

Longest common prefix of a collection of strings


//INPUT : {"ac","abc","abcd"}
//OUTPUT : a

#include<stdio.h>

#define MAX 10000

char * longestcommonprefix(char *a[],int len){
char out[MAX];
// compare ith and i+1th pointers jth character
int flag = 1;
int i;
int j=0;
while(flag){
for(i=0;i<len-1;i++){
//a[i] points to the ith string
if(*(a[i]+j) == *(a[i+1]+j)){
continue;
} else {
flag = 0;
break;
}
}
if(flag){
out[j] = *(a[i]+j);
if(out[j] == '\0') break;
j++;
}
}
out[j] = '\0';
return out;
}

int main(){
char *a[] = {"ac","abc","abcd"};
char *out = longestcommonprefix(a,sizeof(a)/sizeof(char *));
printf("%s",out);
return 0;
}

No comments:

Post a Comment