Please enable JavaScript.
Coggle requires JavaScript to display documents.
String Processing parte 1 - Coggle Diagram
String Processing parte 1
Ad Hoc String processing problems
Cipher/Encode/Encrypt/Decode/Decrypt
Frequency Counting
Input Parsing
Recursive Descent Parser
Regex
Output Formatting
String comparison
Ad hoc
String Matching
Problemas que envolvem encontrar o índice de começo de uma substring em uma string maior
Para strings pequenas basta usar o find de c++
Knuth-Morris-Pratt's (KMP)
Objetivo: Encontrar todas as ocorrências de uma substring
Otimização usar o ganho de informação realizando compações com o caractere anterior
O algoritmo naive pode rodar em O(n) ou no pior caso O(n*m), porém com a otimização o algoritmo roda em O(n+m)
String matching em grid 2D
Requer uma solução com recursive backtracking com poda baseado no tamanho da string que queremos encontrar
Depth-limited-search
String processing with DP
Obs: na maioria dos problemas os índices das strings são manipulados
String Alignment (Edit Distance)
Busca maximizar o score de alinhamento entre duas strings (ou menor quantidade de operações para garantir o score máximo)
Se os caracteres de ambas as strings correspondem e não é necessário nenhuma operação aumentamos o score em +2
Caso contrário, se deletamos um caractere ou inserimos um '_' na string A o atualizamos o score em -1
Longed Common Subsequence