Prince or Impostor
In ancient Persia, during a time of prosperity, there was a great king named Darius. On a joyous day, Darius's son was born, and no one was happier than the king himself. To celebrate, he organized a grand festival. However, amidst the celebrations, assassins hired by Darius's enemies managed to infiltrate the palace and kidnap the newborn prince. Enraged, Darius ordered the execution of the guards and announced a search, promising a substantial reward to anyone who could return his son to the palace.
Days turned into weeks, months, and eventually years, yet there was no sign of the prince. As the eighteenth year of searching began, a tall, slender young man with a spark in his eyes arrived at the palace, claiming to be the lost prince. He recounted an incredible tale of being raised by a humble fisherman's family, who were sworn to secrecy under threat of death. On his deathbed, the old fisherman revealed the young man's true identity.
Darius was inclined to believe the young man, but his vizier advised caution, suggesting a verification process. Every human cell contains DNA, a sequence of nucleotides represented by the symbols A, G, T, and C. These sequences are similar among close relatives. The vizier proposed comparing a fragment of the young man's DNA with the king's DNA, starting from a specific position. Ideally, the fragment would match exactly from that position. However, the degree of similarity would be measured by the number of matching elements. The vizier and the king seek your help to determine the starting position for comparison that yields the highest similarity.
Input
The first line contains the king's DNA sequence, composed of the symbols A, G, T, and C. The second line contains the young man's DNA fragment. Both sequences have a maximum length of 200,000, and the second sequence is not longer than the first.
Output
Output the position number from which to start the comparison to achieve the maximum possible similarity. If multiple positions yield the same similarity, output the first one. Positions are numbered starting from 1.