String matching is a common problem in computer science. One string matching problem is following:
Given a string s[0...len-1], please calculate the longest common prefix of s[i...len-1] and s[0...len-1] for each i>0.
I believe everyone can do it by brute force.
The pseudo code of brute force is following:
the given string is put in array s[0...len-1]
an[i] denote the length of the longest common prefix of s[0...len-1] and s[i...len-1]
for i from 1 to len-1
set k as 0
while i+k less than len
compare s[k] with s[i+k] // here do one time of comparison
if s[k] equal to s[i+k]
k is added by one
otherwise end while loop
set an[i] as k
Now we will introduce another algorithm. It's a not only easy but quick algorithm.
The pseudo code of the algorithm is following:
the given string is put in array s[0...len-1] for i from 1 to len-1
an[i] denote the length of the longest common prefix of s[0...len-1] and s[i...len-1]
W is a window on s which begins with position Wl(Wl >0) and window size is Ws, and s[Wl...Wl+Ws-1] equal to s[0...Ws-1]
In the beginning, set both Wl and Ws as 0
if i greater than Wl+Ws-1
set k as 0
otherwise
set k as min(an[i-Wl], Wl+Ws-i)
while i+k less than len
compare s[k] with s[i+k] // here do one time of comparison
if s[k] equal to s[i+k]
k is added by one
otherwise end while loop
set an[i] as k
if i+k larger than Wl+Ws
set Wl as i, Ws as k
now give you a string. Please print the number of two character's comparison times for the two algorithm.
the first line contain number T,denoting the number of test cases.
Each test case contains one string consisting of printable characters except space.
T<=50
length of string <= 1000000
For each test case, you have to print two number, separately denoting the number of compare time of the two algorithms for calculation the string matching problem by the given pseudo code(the former number is given by brute force).
3 abc aabc ababc
2 2 4 4 6 6
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|