Cifratura Muu#11166
Poche persone sanno che alle mucche piacciono molto i rompicapo, specialmente quelli di parole. Le mucche del contadino John hanno recentemente inventato un divertente rompicapo chiamato "ricerca di parole". Un esempio di tale rompicapo è il seguente:
Poiché le mucche sono, dopotutto, solo mucche, l'unica parola a cui sono interessate è . Questa può comparire nel rompicapo nei modi più svariati: orizzontalmente, verticalmente o diagonalmente. Nell'esempio sopra riportato, la parola compare volte.
Anche il contadino John ama i rompicapo di parole. Poiché le mucche non vogliono che lui risolva il loro rompicapo prima che loro stesse abbiano avuto la possibilità di provarci, lo hanno cifrato utilizzando un "cifrario a sostituzione", che sostituisce ogni lettera dell'alfabeto con un'altra lettera.
Ad esempio, potrebbe essere sostituita da , potrebbe essere sostituita da , e così via. Nessuna lettera viene sostituita da se stessa, e due lettere diverse non vengono mai sostituite dalla stessa lettera, poiché altrimenti la decifrazione risulterebbe ambigua.
Sfortunatamente, le mucche hanno perso l'informazione su quale cifrario a sostituzione sia stato effettivamente utilizzato per cifrare il loro rompicapo. Aiutale a determinare il numero massimo possibile di volte in cui la parola potrebbe essere apparsa nel rompicapo, per un qualche cifrario a sostituzione valido.
La prima riga contiene due interi e m~(1 \le n, m \le 50), che indicano il numero di righe e di colonne del rompicapo.
Le successive righe contengono ciascuna caratteri, che descrivono la riga corrispondente del rompicapo cifrato. Ogni carattere è una lettera maiuscola dell'alfabeto inglese, compresa tra e .
Stampa il numero massimo possibile di volte in cui la parola potrebbe comparire nel rompicapo, dopo averlo decifrato con un opportuno cifrario a sostituzione.
L'esempio riportato è lo stesso rompicapo mostrato all'inizio dell'enunciato, ma a cui è stato applicato un cifrario a sostituzione. In questo esempio, le lettere e sono state sostituite rispettivamente da e .
Esempio 1