performance - Speeding up LCS algorithm for graph construction -

referencing 2nd question inoi 2011:

n people live in sequence land. instead of name, each person identified sequence of integers, called or id. each id sequence no duplicate elements. 2 people said each other’s relatives if ids have @ least k elements in common. extended family of resident of sequence land includes herself or himself, relatives, relatives of relatives, relatives of relatives of relatives, , on without limit. given ids of residents of sequence land, including president, , number k, find number of people in extended family of president of sequence land.

for example, suppose n = 4 , k = 2. suppose president has id (4, 6, 7, 8) , other 3 residents have ids (8, 3, 0, 4), (0, 10), , (1, 2, 3, 0, 5, 8). here, president directly related (8, 3, 0, 4), in turn directly related (1, 2, 3, 0, 5, 8). thus, president’s extended family consists of other (0, 10) , has size 3.

limits: 1 <= n <= 300 & 1 <= k <= 300. number of elements per id: 1-300

currently, solution follows:

1. for every person, compare id other id's using algorithm same lcs, can edited stop searching if k elements aren't there etc. etc. improve it's average case performance. time complexity = o(n^2*k^2)

2. construct adjacency list using previous step result.

3. use bfs. output results

but overall time complexity of algorithm not enough second subtask. googled around little bit, , found solutions similar of mine, , not working larger subtask. thing close solution 1 -> yes, question has been asked previously. reason i'm asking same question again that solution tough work , implement. recently, friend of mine told me better solution read somewhere.

can me create better solution ?

even pointers better solution great.