Resumo Técnico: Correspondência de Permutação sob Orçamentos de Parikh

1. Definição do Problema

O artigo aborda o problema de Correspondência de Padrão de Permutação (Jumbled/Abelian) sobre um alfabeto geral $\Sigma$. Dado um padrão $P$ de comprimento $m$ e um texto $T$ de comprimento $n$, a tarefa clássica é determinar se $T$ contém uma substring de comprimento $m$ cujo multiconjunto de símbolos corresponde ao de $P$. Isso é equivalente a verificar se o vetor de Parikh (vetor de frequência) de uma janela em $T$ é igual ao vetor de Parikh de $P$.

Além da mera detecção, os autores estendem o escopo para duas variantes de otimização:

1. Subsequência Máxima Viável sob Suprimento de Padrão (MFSP - Maximum Feasible Substring under Pattern Supply): Tratando as contagens de símbolos de $P$ como um orçamento de recursos (vetor de suprimento), o objetivo é encontrar a substring mais longa $S$ de $T$ tal que as contagens de símbolos de $S$ sejam componente a componente limitadas pelas de $P$ (ou seja, $freq(S) \preceq freq(P)$).
2. Seleção Não Sobreposta: Dado um conjunto de todas as correspondências de permutação em $T$, selecionar o subconjunto de maior cardinalidade dessas correspondências de modo que nenhuma duas correspondências selecionadas se sobreponham. Como todas as correspondências têm comprimento $m$, isso é modelado como um problema de empacotamento de intervalos.

2. Metodologia e Algoritmos

O artigo propõe uma estrutura unificada baseada em algoritmos de janela deslizante e manutenção de diferença de vetor de Parikh.

2.1 Correspondência de Permutação em Tempo Linear (Linha de Base)

Os autores apresentam um algoritmo para detectar ocorrências de permutação em $O(n + \sigma)$ tempo e $O(\sigma)$ espaço, onde $\sigma = |\Sigma|$.

• Mecanismo: Em vez de recalcular os vetores de frequência para cada janela, o algoritmo mantém um vetor de diferença $\Delta_i(c) = freq(W_i)(c) - freq(P)(c)$ para a janela atual $W_i$.
• Otimização: Um único contador inteiro, $nz_i$, rastreia o número de entradas não nulas em $\Delta_i$. Uma janela é uma correspondência se, e somente se, $nz_i = 0$.
• Atualizações: Quando a janela desliza, apenas duas coordenadas de $\Delta$ mudam (um caractere sai, um entra). O algoritmo atualiza $nz$ em tempo constante com base em se uma coordenada cruza o zero.

2.2 MFSP: Subsequência Máxima Viável

Para resolver a variante de empacotamento, os autores introduzem um algoritmo de dois ponteiros (janela deslizante) que também roda em $O(n + \sigma)$ tempo.

• Mecanismo: O algoritmo mantém uma janela $T[\ell..r]$ e um array de contagem cnt para a janela atual. Um contador de violação viol rastreia quantos símbolos excedem seu orçamento definido por $freq(P)$.
• Lógica: O ponteiro direito $r$ expande a janela. Se a adição de um caractere causar uma violação (ou seja, cnt excede sup), o ponteiro esquerdo $\ell$ avança até que a viabilidade seja restaurada.
• Corretude: O algoritmo baseia-se na monotonicidade da viabilidade: encolher uma janela pela esquerda nunca aumenta as contagens de símbolos. A prova estabelece que, para cada extremidade direita $r$, o algoritmo encontra a subsequência mais longa viável terminando em $r$, garantindo a otimalidade global.

2.3 Seleção Não Sobreposta via Empacotamento de Intervalos

Uma vez que todas as correspondências de permutação são enumeradas (usando o algoritmo de linha de base), o problema de seleção é resolvido via uma estratégia gulosa.

• Mecanismo: Como todas as correspondências correspondem a intervalos de comprimento igual $m$, o problema reduz-se a selecionar o número máximo de intervalos disjuntos.
• Estratégia: O algoritmo percorre o texto da esquerda para a direita, selecionando a primeira correspondência disponível e então saltando $m$ posições para a próxima potencial correspondência não sobreposta.
• Prova: Um argumento de troca demonstra que esta regra gulosa de "término mais cedo" (ou início mais cedo, dado os comprimentos iguais) produz um conjunto de cardinalidade máxima.

3. Principais Contribuições

1. Estrutura Unificada: Uma abordagem concisa de janela deslizante que lida com detecção, otimização (MFSP) e seleção usando manutenção de diferença de Parikh.
2. Complexidade Ótima: Todos os algoritmos propostos alcançam $O(n + \sigma)$ de tempo e $O(\sigma)$ de espaço. Isso coincide com o limite inferior para leitura da entrada e é ótimo para alfabetos gerais.
3. Formulação MFSP: A introdução do problema MFSP, que reformula a correspondência jumbled como um problema de empacotamento restrito por recursos, resolvido com um algoritmo de dois ponteiros linearmente correto.
4. Otimalidade Gulosa: Uma prova formal de que uma varredura gulosa simples é ótima para selecionar correspondências de permutação não sobrepostas quando todas as correspondências têm o mesmo comprimento.

4. Resultados e Observações Experimentais

Os autores relatam observações experimentais leves para corroborar seus limites teóricos:

• Escalabilidade: Tanto a correspondência de permutação quanto o MFSP exibem escalonamento linear com o comprimento do texto $n$, consistente com a análise $O(n + \sigma)$.
• Fatores de Desempenho: O tempo de execução é dominado pelos padrões de acesso à memória dos arrays/mapas de contagem e pela densidade das correspondências (que afeta o volume de saída, mas não a lógica de varredura).
• Tratamento de Alfabeto: Para alfabetos grandes, a compressão de alfabeto (mapeando símbolos que aparecem em $P$ e $T$ para inteiros $1 \dots \sigma'$) reduz significamente a pegada de memória e melhora a localidade de cache, mantendo a eficiência mesmo quando $\sigma$ é grande, mas $\sigma'$ é pequeno.
• Eficiência do MFSP: O mecanismo de contador de violação no MFSP evita verificações completas de viabilidade, garantindo que cada caractere seja adicionado ou removido no máximo uma vez, aderindo à amortização padrão de dois ponteiros.

5. Significância e Escopo

O artigo posiciona a correspondência de strings baseada em frequência não apenas como uma tarefa de detecção, mas como uma fundação para primitivas de otimização combinatória.

• Contribuição Teórica: Conecta o problema clássico de correspondência jumbled à otimização de estilo empacotamento, fornecendo limites apertados e algoritmos concisos.
• Utilidade Prática: Os algoritmos são projetados para varredura de passagem única, tornando-os adequados para aplicações que exigem processamento em tempo real ou otimização sob restrições de recursos (ex: orçamentos de tokens no processamento de texto).
• Modéstia: Os autores declaram explicitamente que seu foco está em primitivas de detecção e otimização, em vez de construção de índices para múltiplas consultas. Eles reconhecem que trabalhos futuros poderiam explorar extensões ponderadas ou aproximadas de MFSP, mas a contribuição atual é estritamente limitada a soluções exatas de tempo linear para os problemas definidos.

O trabalho conclui que, ao manter as diferenças do vetor de Parikh e utilizar estratégias simples de dois ponteiros ou gulosas, é possível resolver variantes complexas de correspondência de permutação com corretude provável e complexidade de tempo linear ótima.