Programming Principles 1. Week 6. October 7 - 13. PART 2
The data is transmitted from the transmitter to the receiver via a communication channel in the form of a bit sequence. Features of the communication channel are such that during the transmission of a sequence of bits, some distortions may be introduced into it. Thus, the bit sequence t received by the receiver may be different from the s sequence transmitted by the transmitter. One of the types of distortion that can be introduced during the transmission is the so-called transposition of neighboring bits. With this distortion, s and t differ exactly in two adjacent positions i and i + 1, with
ti, and for all j ≠ i, j ≠ i + 1 the equality
ti is true.
You are one of the researchers dealing with problems of information transfer. Currently you are working on a coding system for an important government communication channel. The code you develop must have the property of correcting one transposition of neighboring bits. In order for the code being developed to be as efficient as possible, you need to obtain information about the reliability level of this channel. Reliability is tested in the following way: the sequence of bits
sn is transmitted over the channel, the sequence
t2 , ...,
tn that was received by the receiver is remembered, and then compared with transmitted. Based on how much of the sequence is transmitted without distortion or with a single transposition, the conclusion is made about the reliability of the channel.
Since the sequence selected for transmission is long enough, it is very laborious to perform their comparison manually. So you decided to write a program that performs this comparison.
Write a program that, according to two given sequences s and t, determines whether it is possible to get t from s by performing at most one transposition of neighboring characters.
First line contains the sequence s, second line contains the sequence t. Both sequences are non-empty, containing only zeros and ones, and have length no more than
If the sequence t can be obtained from the sequence s in the specified way, print YES, otherwise print NO.