Copiado al portapapeles
Descripción
No hay tiempo para historias largas y aburridas.
Se te dan dos cadenas, \( S \) y \( T \), de longitudes \( N \) y \( M \) respectivamente.
Puedes realizar la siguiente operación en cualquiera de las cadenas: Reemplazar una subcadena con su primer carácter. (por ejemplo, "abcabc" -> "abcc")
¿Cuál es el número mínimo de operaciones para hacer que ambas cadenas sean iguales? O determina si es imposible hacer que ambas cadenas sean iguales.
Entrada
La primera línea de entrada contiene un solo entero \( T \) $(1 \leq T \leq 10^5)$, que denota el número de casos de prueba.
La primera línea de cada caso de prueba consiste en dos enteros separados por espacio \( N \) y \( M \) $(1 \leq N, M \leq 2 \cdot 10^5)$, que denotan las longitudes de las cadenas \( S \) y \( T \), respectivamente.
La segunda línea de cada caso de prueba contiene la cadena \( S \) de longitud \( N \).
La tercera línea de cada caso de prueba contiene la cadena \( T \) de longitud \( M \).
La suma de \( N \) sobre todos los casos de prueba no excederá \( 2 \cdot 10^5 \).
La suma de \( M \) sobre todos los casos de prueba no excederá \( 2 \cdot 10^5 \).
Salida
Para cada caso de prueba, imprime una sola línea que contenga un solo entero que denote el número mínimo de operaciones necesarias para hacer que las cadenas sean iguales, o \( -1 \) si no es posible hacerlo.
Ejemplo Entrada
3 4 3 aabc aab 8 8 accepted accapted 1 1 z z
Ejemplo Salida
1 2 0
Ayuda
Caso de prueba 1:
$\begin{itemize}
Puedes hacer que S sea igual a \( T \) utilizando una operación en \( S \): "aabc" -> "aab".
\end{itemize}$
Caso de prueba 2:
$\begin{itemize}
Se puede demostrar que necesitas al menos dos operaciones para hacer que las cadenas sean iguales. Una posible forma es la siguiente:
Realizar una operación en \( S \): "accepted" -> "accpted".
Realizar una operación en \( T \): "accapted" -> "accpted".
\end{itemize}
$
Caso de prueba 3: Ambas cadenas ya son iguales.