PROGRAMMING:Gene sequence of a new coronavirus
In the last ten days of December 2019, there were many cases of viral pneumonia of unknown causes in Wuhan. Later, the Chinese Center for Disease Control and prevention identified the pathogen as a new coronavirus. In January 12th, WHO named it "2019 New Coronavirus (2019-nCoV)". In order to understand the origin of New Coronavirus, researchers from China CDC and other institutions conducted high throughput sequencing of the hospitalized patients and obtained complete and partial 2019-nCoV genome sequences. Then, phylogenetic analysis of these 2019 ncov genomes and other coronavirus genomes was carried out to determine the evolutionary history of these viruses and help infer their possible sources.
The above research belongs to the cross field of computer and biomedical research, we call it bioinformatics. In bioinformatics, we take DNA as an example to illustrate the similarity of gene sequences. DNA (deoxyribonucleic acid) is the main genetic material in life, which can transmit genetic information from parents to offspring. It is a kind of linear polydeoxyribonucleic acid, which is composed of bases, pentose and phosphoric acid. The main chain of all DNA is the same, except adenine (a), guanine (g), guanine (g) The sequence of cytosine (c) and thymine (T) is different. The DNA of different organisms has its own unique base sequence, and the genetic information is reflected by the base sequence. Therefore, it is very important to compare the DNA sequences (that is, to observe the sequence of the four bases on the main chain), So we can infer the distance of the relationship between species.
Now I'll give you two strings composed of four letters of AGCT. Please find out the longest common subsequence of the two DNA sequences.
###Input format:
Two lines, one string for each line, representing a DNA sequence (each string length does not exceed 1000).
###Output format:
The number of the longest common subsequence elements.
###Input example:
Here is a set of inputs. For example:
```in
AGCT
ATT
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
answer：If there is no answer, please comment
The above research belongs to the cross field of computer and biomedical research, we call it bioinformatics. In bioinformatics, we take DNA as an example to illustrate the similarity of gene sequences. DNA (deoxyribonucleic acid) is the main genetic material in life, which can transmit genetic information from parents to offspring. It is a kind of linear polydeoxyribonucleic acid, which is composed of bases, pentose and phosphoric acid. The main chain of all DNA is the same, except adenine (a), guanine (g), guanine (g) The sequence of cytosine (c) and thymine (T) is different. The DNA of different organisms has its own unique base sequence, and the genetic information is reflected by the base sequence. Therefore, it is very important to compare the DNA sequences (that is, to observe the sequence of the four bases on the main chain), So we can infer the distance of the relationship between species.
Now I'll give you two strings composed of four letters of AGCT. Please find out the longest common subsequence of the two DNA sequences.
###Input format:
Two lines, one string for each line, representing a DNA sequence (each string length does not exceed 1000).
###Output format:
The number of the longest common subsequence elements.
###Input example:
Here is a set of inputs. For example:
```in
AGCT
ATT
```
###Output example:
The corresponding output is given here. For example:
```out
two
```
answer：If there is no answer, please comment