http://uva.onlinejudge.org/external/115/11548.html
This problem statement tried to mislead you with some weird game between two characters Alice and Bob. Let's not put to much attention in that and focus in the the real task:
Given \(n (2 \leqslant n \leqslant 70) \) strings, you need to return the length of the best vertical alignment between an arbitrary pair of strings \(S_{i}\), \(S_{j}\) where \(i \neq j\). What exactly does that mean? Let's take a look to an example to clear out some obscures points of this statement:
The following two pictures shows two possible alignments for the strings "ABCD" and "ADC", among them the second one is the best alignment which include the letters A and C for a total length of 2.
The constraints of this problem are not to high, to solve it we can simply iterate over all the possible pair of strings, and for each of them calculate all the possible alignments and keep the length of the best one.
The hardest part perhaps is the procedure to calculate the best alignment for a given pair of strings. In order to do that, we just need to take one of the string as point of reference, let's call this string \(S\) and the another string \(P\), at each step we start to compare each character of \(S\) with each character of \(P\), once we are done we repeat the process but now, beginning in the next letter of the string \(S\). During this process if one the string reach it's last letter we restart the counter of matches, and start to count again from the current position, which is equivalent to begin another alignment.
This may sound a little bit confusing let's take a look to an example:
The previous picture simulates the idea of the algorithm as we can see using this method we consider all the possible alignments between "ABCD" and "ADC".
The overall time complexity of this solution is \(O(N^{4})\).
This problem statement tried to mislead you with some weird game between two characters Alice and Bob. Let's not put to much attention in that and focus in the the real task:
Given \(n (2 \leqslant n \leqslant 70) \) strings, you need to return the length of the best vertical alignment between an arbitrary pair of strings \(S_{i}\), \(S_{j}\) where \(i \neq j\). What exactly does that mean? Let's take a look to an example to clear out some obscures points of this statement:
The following two pictures shows two possible alignments for the strings "ABCD" and "ADC", among them the second one is the best alignment which include the letters A and C for a total length of 2.
The constraints of this problem are not to high, to solve it we can simply iterate over all the possible pair of strings, and for each of them calculate all the possible alignments and keep the length of the best one.
The hardest part perhaps is the procedure to calculate the best alignment for a given pair of strings. In order to do that, we just need to take one of the string as point of reference, let's call this string \(S\) and the another string \(P\), at each step we start to compare each character of \(S\) with each character of \(P\), once we are done we repeat the process but now, beginning in the next letter of the string \(S\). During this process if one the string reach it's last letter we restart the counter of matches, and start to count again from the current position, which is equivalent to begin another alignment.
This may sound a little bit confusing let's take a look to an example:
The previous picture simulates the idea of the algorithm as we can see using this method we consider all the possible alignments between "ABCD" and "ADC".
The overall time complexity of this solution is \(O(N^{4})\).
No comments:
Post a Comment