heres mah code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char string1[128], string2[128];
int len1, len2;
int lcslen;
int lcsorder[128][128];
void calc_lcsorder(void){
static int forward[128][128], backward[128][128];
int i,j;
forward[0][0]=(string1[0]==string2[0]);
for(i=1;i<len1;i++) forward[i][0]=forward[i-1][0]||(string1[i]==string2[0]);
for(j=1;j<len2;j++) forward[0][j]=forward[0][j-1]||(string1[0]==string2[j]);
for(i=1;i<len1;i++) for(j=1;j<len2;j++){
if(string1[i]==string2[j]) forward[i][j]-forward[i-1][j-1]+1;
else forward[i][j]=(forward[i][j-1]>forward[i-1][j])?forward[i][j-1]:forward[i-1][j];
}
backward[len1-1][len2-1]=(string1[len1-1]==string2[len2-1]);
for(i=len1-2;i>=0;i--) backward[i][len2-1]=backward[i+1][len2-1]||(string1[i]==string2[len2-1]);
for(j=len2-2;j>=0;j--) backward[len1-1][j]=backward[len1-1][j+1]||(string1[len1-1]==string2[j]);
for(i=len1-2;i>=0;i--) for(j=len2-2;j>=0;j--){
if(string1[i]==string2[j]) backward[i][j]=backward[i+1][j+1]+1;
else backward[i][j]=(backward[i][j+1]>backward[i+1][j])?backward[i][j+1]:backward[i+1][j];
}
lcslen=backward[0][0];
for(i=0;i<len1;i++) for(j=0;j<len2;j++){
if((string1[i]==string2[j])&&(forward[i][j]+backward[i][j]==lcslen+1)) lcsorder[i][j]=forward[i][j];
else lcsorder[i][j]=0;
}
}
typedef struct{
int level;
char letter;
int idx1, idx2;
}t_occurence;
int compare_occurences(const void *ptr1, const void *ptr2){
t_occurence *o1=(t_occurence *)ptr1;
t_occurence *o2=(t_occurence *)ptr2;
int d;
if(d=o1->level-o2->level) return d;
if(d=o1->letter-o2->letter) return d;
if(d=o1->idx1-o2->idx1) return d;
return o1->idx2-o2->idx2;
}
int occurences;
t_occurence occurence[128*128];
int firstoccurence[128];
void make_occurences(void){
int i,j;
occurence[0]=(t_occurence){0,'*',-1,-1};
occurences=1;
for(i=0;i<len1;i++) for(j=0;j<len2;j++) if(lcsorder[i][j]){
occurence[occurences++]=(t_occurence){lcsorder[i][j],string1[i],i,j};
}
qsort(occurence,occurences,sizeof(t_occurence), compare_occurences);
firstoccurence[0]=0;
for(i=1;i<occurences;i++) if(occurence[i].level!=occurence[i-1].level){
firstoccurence[occurence[i].level]=i;
}
occurence[occurences]=(t_occurence){1000,'*',-1,-1};
}
char currenttrip[128];
void find_trips(int prev){
int i, level;
if(occurence[prev].level==lcslen){
currenttrip[lcslen]='\0';
printf("%s\n",currenttrip);
return;
}
level=occurence[prev].level+1;
currenttrip[level-1]='*';
for(i=firstoccurence[level];occurence[i].level==level;i++){
if(occurence[i].idx1<=occurence[prev].idx1) continue;
if(occurence[i].idx2<=occurence[prev].idx2) continue;
if(occurence[i].letter==currenttrip[level-1]) continue;
currenttrip[level-1]=occurence[i].letter;
find_trips(i);
}
}
int main(){
int cases;
scanf("%d", &cases);
while(cases--){
scanf("%s", string1);
len1=strlen(string1);
scanf("%s", string2);
len2=strlen(string2);
calc_lcsorder();
make_occurences();
find_trips(0);
if(cases) printf("\n");
}
return 0;
}
help?
