Cómo resolver el problema 144C en Codeforces

2 cadenas A y B si y solo si el recuento de cada letra (‘a’ … .’z ‘) en ambas cadenas es el mismo. De ello se deduce que ambas cadenas serán de igual longitud. Ahora se nos han dado algunos caracteres comodín en la cadena A. Un carácter comodín puede aumentar el recuento de cualquiera de las letras en A en 1.

Ahora,
Permítanos almacenar el recuento de cada letra en la cadena p en una matriz de pc []. Supongamos que tenemos el recuento de cada letra para la subcadena a partir del índice i de la cadena s (que tiene la misma longitud que la de p) en la matriz sic [], también tenemos el número de caracteres comodín en la subcadena dada. Podemos verificar fácilmente si pueden convertirse en anagramas o no.

bool check(int sic[], int wcard) { int diff = 0; // diff is the count of wild card characters required to make the anagram for(int i=0; i pc[i]) return false; // if count in p is more, we add it to the number of wild chard characters required else diff += (pc[i] - sic[i]); } return (diff <= wcard); } 

La pregunta ahora es cómo actualizaremos la matriz sic [] y wcard. Observe que al pasar de la iteración i-1 a i, solo necesitamos eliminar s [i-1] (o decrementar wcard) y agregar s [i + p.length () – 1] (o aumentar wcard). Usando esto…

• ¿Qué libro debo elegir para estudiar la estructura de datos en lenguaje C?
• Cómo equilibrar el tiempo entre el desarrollo web de aprendizaje (JavaScript) y las estructuras de datos de algoritmos
• ¿Cuáles son algunos de los recursos disponibles para los estudiantes de informática en predicción de la estructura secundaria de ARN?
• Gráfico distribuido: ¿Cuál es la forma más efectiva de distribuir los nodos de un gráfico en diferentes servidores en un sistema distribuido?
• ¿Qué es más importante, aprender múltiples lenguajes de programación o practicar algoritmos?

 i=1; while(i + p.length() - 1 < s.length()) { // removing s[i-1] if(s[i-1] == '?') wcard--; else sic[ s[i-1]-'a' ]--; // adding s[i + p.length() - 1] if(s[i + p.length() - 1] == '?') wcard++; else sic[ s[i+p.length()-1]-'a' ]++; if(check(sic, wcard)) ans++; i++; } 

Al principio, tendremos que hacer las matrices sic [] así como pc [].

 memset(pc, 0, sizeof(pc)); for(int j=0; j<p.length(); j++) pc[ p[j] - 'a' ]++; int sic[26] = {0}; int ward=0; if(p.length() <= s.length()) { for(int j=0; j<p.length(); j++) { if(s[j] == '?') wcard++; else sic[ s[j]-'a' ]++; } } if(check(sic, wcard)) ans++;