Нахождение взаимной подпоследовательности в связанных списках

Question

Попытка найти и вернуть самую длинную взаимную подпоследовательность из 2 связанных списков. Сложность должна быть O (m * n) в худшем случае и O (m + n) в лучшем случае.

В списках может быть 1 из 3 вариантов: обычный, двусторонний связанный список или круговой связанный список.

На данный момент у меня есть (псевдокод):

mutualMaxSubNodes(lst1, lst2):
 x<-head(lst1)
 y<-head(lst2)
 createlist(lst3)
 w<-head(lst3)
 maxcounter=0
 while (next(x)!=NULL)
       while (next(y)!=NULL)
            counter=0
            z=x
            t=y
            while(z==t)&&(z!=NULL)||t!=NULL)
                 counter++
                 if(maxcounter<counter)
                      maxcounter=counter
                      lst3=x //havn't thought about how to pass this to the new list yet
                  z<-next(z)
                  t<-next(t)
            y<-next(y)
  x<-next(x)
  y<-head(lst2)

the probelm : Это первые 2 - мои входные данные, а lst3 - то, что я нужно вернуть

Я также думал о создании такой матрицы каждый раз, когда я добираюсь до точки, где 2 "индекса" равны, я добавляю 1 к количеству - это число в диагонали , а затем сохраняет самый высокий из них. но все же, не соответствует требованиям

Кстати - извините за грязный пост. Первый раз и не могу заставить изображения работать