求问一道算法题~# JobHunting - 待字闺中
c*x
1 楼
Question:
There are 1000 distinct strings, each string is composed by the chars in{‘a
','b','c','d'}. And each string.Length()==30;
here's a function aims at calculating the overlap of two different strings；
int overlapNumber(string str1, string str2){...}
overlapNumber is the length of largest prefix of str2 which is contained by
str1(Not necessary the surfix of str1)
and what I want is to calculate all the overlapNumbers between every two
strings within this string sets.
Notice: overlap(str1,str2) is sometimes not equal to overlap(str2,str1).
=========================================================================
My Solution:
My solution is somehow straightforward:
I change a little bit of the KMP string match algorithm and calculate every
two strings within this sets.
This takes O(n^2)
=========================================================================
Any Da Shen has a better solution?
I'm thinking of using tries...will it help?
Thanks!
There are 1000 distinct strings, each string is composed by the chars in{‘a
','b','c','d'}. And each string.Length()==30;
here's a function aims at calculating the overlap of two different strings；
int overlapNumber(string str1, string str2){...}
overlapNumber is the length of largest prefix of str2 which is contained by
str1(Not necessary the surfix of str1)
and what I want is to calculate all the overlapNumbers between every two
strings within this string sets.
Notice: overlap(str1,str2) is sometimes not equal to overlap(str2,str1).
=========================================================================
My Solution:
My solution is somehow straightforward:
I change a little bit of the KMP string match algorithm and calculate every
two strings within this sets.
This takes O(n^2)
=========================================================================
Any Da Shen has a better solution?
I'm thinking of using tries...will it help?
Thanks!
