Ο Μίλτος το δελφίνι θέλησε να στείλει ένα μήνυμα σε κάποιον φίλο του στην άλλη πλευρά του Βυθού. Για να μην υποκλαπεί το μήνυμά του από κάποιον τρίτο, αποφάσισε να διαλέξει μια λέξη ως κρυφό κλειδί, με τη βοήθεια της οποίας θα κρυπτογραφήσει το κείμενό του. Για να το κάνει αυτό, άνοιξε το πιο μεγάλο βιβλίο που είχε στο σπίτι του, διάλεξε στην τύχη ένα κομμάτι του κειμένου και το έγραψε σε ένα χαρτί. Για κακή του τύχη όμως, μπερδεύτηκε και υπάρχει περίπτωση να έκανε λάθος σε κάποιο χαρακτήρα, δηλαδή αντί για τον σωστό να έγραψε κάποιον άλλον. Ευτυχώς, δεν είναι τόσο απρόσεκτος ώστε να έχει κάνει πολλά λάθη, οπότε το πολύ ένας χαρακτήρας μπορεί να είναι λάθος.
Σας δίνεται το κείμενο του βιβλίου από το οποίο ο Μίλτος διάλεξε το κλειδί του, καθώς και το κλειδί του, με το πολύ έναν λανθασμένο χαρακτήρα. Τώρα, ο Μίλτος αναρωτιέται πόσα δυνατά κομμάτια κειμένου υπάρχουν, τα οποία θα μπορούσαν να είναι το κλειδί του.
Συγκεκριμένα, σας δίνεται μία συμβολοσειρά S, η οποία είναι το κείμενο του βιβλίου, καθώς και μία συμβολοσειρά T, η οποία είναι το (πιθανώς λάθος) κλειδί που έχει καταγράψει ο Μίλτος. Πόσες υποσυμβολοσειρές της S υπάρχουν, οι οποίες διαφέρουν μόνο σε μία θέση από την T;
Στην πρώτη γραμμή δίνεται η συμβολοσειρά S και στη δεύτερη η T.
Ένας ακέραιος, το πλήθος των υποσυμβολοσειρών της S από τις οποίες θα μπορούσε να προέρχεται η T.
Όλες οι συμβολοσειρές περιέχουν αποκλειστικά μικρούς λατινικούς χαρακτήρες. Επίσης κάθε συμβολοσειερά περιέχει τουλάχιστον 1 και το πολύ 1.000.000 χαρακτήρες. Το μήκος της S δεν θα είναι μικρότερο αυτού της T.
(Περίπου 20% των παραδειγμάτων εισόδου θα περιέχουν συμβολοσειρές που έχουν παραχθεί με ομοιόμορφα τυχαίο τρόπο)
miltosossos tos
3