Por que este artigo?
Após acreditar ter dominado os algoritmos de strings[1], uma experiência prática com problemas de correspondência revelou que talvez nunca tivesse compreendido completamente o algoritmo KMP. Este artigo nasce dessa reflexão.
Portanto, este não é apenas um tutorial sobre algoritmos de strings, mas também um registro do processo de aprendizado.
Como diz o velho ditado: "Revisar o conhecimento antigo para adquirir novo conhecimento, pode-se ser mestre". Essa abordagem de aprendizagem também é conhecida como método de aprendizagem de Feynman.
Assim, após ler este artigo, você poderá ensinar aos outros, explicando-lhes que se trata de um método avançado de aprendizagem.
Público-alvo
Este artigo destina-se a pessoas que já estudaram algoritmos de strings mas ainda não os compreendem totalmente.
Se você nunca estudou strings, recomenda-se primeiro entender os conceitos básicos em recursos como OI-wiki.
Se não entender imediatamente as ideias fundamentais dos algoritmos, não se preocupe - pode revisitar este artigo mais tarde.
Se você é um especialista no assunto, também é bem-vindo a ler criticamente este artigo com uma perspectiva superior. O autor tem conhecimentos limitados e uma formação modesta[2], e apreciaria correções de especialistas caso encontrem erros.
O que será abordado
Focaremos nas ideias centrais dos algoritmos, não apenas em explicações superficiais.
Devido à experiência limitada do autor, podem existir erros. Críticas e correções são bem-vindas.
Se houver tópicos menos conhecidos que você gostaria de ver, pode sugerir por mensagem privada, e eles serão incluídos se o autor conseguir compreendê-los.
Fundamentos de Strings
Conjunto de Caracteres
Ao longo dos anos de estudo superficial, o autor acumulou alguma compreensão. E sobre os "fundamentos", o primeiro conceito deve ser o "conjunto de caracteres".
Ao contrário dos "domínios" comuns, os conjuntos de caracteres em strings geralmente são pequenos.
Por exemplo, no autômato AC clássico, o motivo pelo qual ele opera com complexidade relativamente baixa é que o conjunto de caracteres é extremamente pequeno em comparação com outras estruturas de dados. Na maioria das vezes, o tamanho do conjunto de caracteres é considerado constante.
Em geral, o tipo char é suficiente para lidar com todos os conjuntos de caracteres possíveis em competições de programação.
Ordem Lexicográfica
Se a segunda pergunta sobre os conceitos fundamentais das strings (além do tamanho do conjunto de caracteres) é qual, a resposta deve ser a ordem lexicográfica.
Na verdade, a aplicação da ordem lexicográfica não se limita às strings - muitos problemas não relacionados também usam conceitos semelhantes, como comparar números em sequências.
É importante notar as diferenças e conexões com a comparação numérica comum. Para entender melhor, pode-se consultar as discussões relacionadas ao problema [NOIP 1998 Grupo Avançado] "Juntar Números", que contém algumas discussões sobre relações de ordem parcial[4].
Na implementação, duas strings podem ser comparadas caractere por caractere. A complexidade de tempo é \(O(N)\), onde \(N\) é o comprimento da string (se considerarmos o custo de entrada da string em si, será o comprimento da string mais longa; caso contrário, será o da string mais curta).
Divisão e Concatenação
O que mais distingue strings de outras estruturas de dados é que cada caractere pode ser considerado "independente". Portanto, você pode dividir uma string ao meio ou concatenar duas strings. Essas duas operações aparecem na maioria dos problemas envolvendo strings. Geralmente, um "prefixo" é obtido dividindo a primeira parte, enquanto um "sufixo" é obtido dividindo a última parte. Pode-se também pensar em termos de exclusão de caracteres: um "prefixo" seria excluir a parte final, enquanto um "sufixo" seria excluir a parte inicial.
O tipo string em C++ fornece operadores convenientes como + e substr para executar essas operações. É importante notar que a adição interna do tipo char em C++ é baseada na adição e subtração de inteiros do código ASCII, não na concatenação de strings. A abordagem correta é converter primeiro para string antes de realizar operações. Se for necessário converter int ou outros tipos para string, sstream é uma boa opção.
Hash (Hashing)
Hashes únicos podem ser vulneráveis a colisões, enquanto hashes duplas podem reduzir significativamente a probabilidade de colisões (mas não eliminá-las completamente).
Eles permitem verificar rapidamente se duas strings são iguais, mas não são convenientes para comparar ordem lexicográfica (para isso, são necessárias algumas técnicas especiais).
Se todas as strings no espaço de strings forem hashizadas, certamente haverá colisões. Mas na maioria das vezes, os problemas exigem apenas uma pequena fração do espaço total de strings. (O número de strings é extremamente pequeno em comparação com todas as possíveis strings do comprimento correspondente). Às vezes, dentro das limitações de comprimento impostas pelo problema, nenhuma string pode causar colisões de hash. É por isso que os algoritmos de hash são quase sempre corretos na maioria dos casos.
Na implementação, pode-se usar uma abordagem semelhante a polinômios, multiplicando por um coeficiente a cada caractere. Para mais detalhes, consulte OI-Wiki ou os links relacionados no final do artigo.
Estes quatro pilares podem ser considerados fundamentais para o domínio de strings.
Primeiro Destino: KMP (Parte 1)
Se perguntarmos qual é o algoritmo de correspondência de strings mais clássico, a resposta deve ser o KMP.
Para entender por que o algoritmo KMP recebe esse nome, consulte: "FAST PATTERN MATCHING IN STRINGS", DONALD E. KNUTH, JAMES H. MORRIS, JR. E VAUGHAN R. PRATT.
Há uma nota de estudo anterior sobre KMP, mas está desatualizada.
O artigo original já explica detalhadamente o algoritmo, mas é bastante denso e difícil de entender. O apresentará aqui a partir de outra perspectiva.
KMP é essencialmente um algoritmo de correspondência de strings que requer encontrar todas as ocorrências da string padrão \(S\) (comprimento \(m\)) na string de texto \(T\) (comprimento \(n\)).
Primeiro, consideremos o algoritmo de correspondência ingênuo. Para cada posição em \(T\), usamos como ponto de partida e tentamos corresponder \(S\) caractere por caractere. Se houver falha, simplesmente pulamos para a próxima posição.
É fácil notar que o que realmente consome tempo não é a falha na correspondência, mas o sucesso. Se todas as tentativas corresponderem falharem, a complexidade de tempo do algoritmo seria \(O(n)\). No entanto, se todas corresponderem com sucesso (por exemplo, \(S\) e \(T\) consistem no mesmo caractere \(a\) repetido), a complexidade de tempo atingiria \(O(nm)\).
Como podemos reduzir o número de correspondências?
O sucesso na correspondência, embora consuma tempo adicional, certamente nos fornece alguma "informação".
Similarmente a como problemas de subconjunto soma são resolvidos com programação dinâmica em vez de busca, a essência é mesclar estados com o mesmo espaço total. Mas a busca é completamente inútil? Em alguns casos com grandes domínios de valores mas poucas instâncias, a busca pode encontrar soluções independentemente do domínio de valores, o que é difícil de alcançar com programação dinâmica comum.
A seção anterior pode envolver alguns conhecimentos de teoria da informação, mas como o autor é um iniciante, não exploraremos isso em profundidade.
Vamos pensar no que o "sucesso na correspondência" nos informa. Suponha que a parte correspondente com sucesso seja \(S[1, j]\) em \(T[i, i + j - 1]\) (usando indexação 1, ou seja, \(S[1, j]\) é um prefixo de \(S\)). Isso significa que cada caractere desse prefixo corresponde aos caracteres correspondentes em \(T\).[5]
Leitores podem primeiro pensar por si mesmos como usar essa ideia para otimizar o algoritmo antes de prosseguir.
Para evitar spoilers:
Construção
Para simplificar, vamos considrear \(i\) e \(j\) como monotonicamente crescentes.
Considere os casos de falha ou sucesso na correspondência. Neste ponto, \(S_{j+1} \ne T_{i+j}\). O sucesso na correspondência pode ser tratado como uma falha no próximo caractere quando \(j = m\) (ou seja, não há \(S_{m+1}\) válido para corresponder).
(No momento, não temos nenhuma informação sobre a parte de \(T\) após \(i+j\))
Neste ponto, procuramos o maior \(i'\) possível tal que, com as informações existentes, não possa existir \(k\) com \(i < k < i'\) que permita que \(T\) corresponda com sucesso a \(S\). Isso garante a correção. Podemos então iniciar a próxima tentativa de correspondência diretamente em \(i'\). Ao mesmo tempo, queremos encontrar um \(j'\) que possa ser usado diretamente na próxima correspondência.
Para o caso onde \(i' > i+j-1\), como não temos informações sobre o que vem depois, só podemos começar tentando corresponder com \(j' = 1\). Mas o objetivo já foi alcançado: o intervalo \(i \sim i+j-1\) foi pulado, economizando tempo usando as informações existentes.
Para \(i' \le i+j-1\), existe uma parte válida \(T[i',i+j-1]\. Como queremos que seja possível corresponder com sucesso, exigimos que \(T[i', i+j-1] = S[1, j+i-i']\. Notando que pelas condições existentes, deve valer \(T[i', i+j-1] = S[i'-i+1, j]\.
(Quando \(i'-i+1 < j+i-i'\), a dedução ainda é válida)
Como não exigimos nenhuma condição adicional, para \(i' \le i+j-1\), \(i'\) deve satisfazer \(S[1, j+i-i'] = S[i'-i+1, j]\, ou seja, no prefixo \(S[1, j]\, o "prefixo do prefixo" \(S[1, j+i-i']\ é igual ao "sufixo do prefixo" \(S[i'-i+1, j]\.
Considere encapsular \(j+i-i'\) em algo relacionado apenas a \(S\). Seja \(next_j\) o maior \(x\) tal que \(S[1, x] = S[j-x+1, j], x < j\) para \(S[1, j]\. A hipótese é que o ótimo seria \(i' = j + i - next_j\).
Se existir um \(k\) tal que \(i < k < i'\) e seja válido, então pelo exposto, deve valer \(S[1, j+i-k] = S[k-i+1, j]\, o que contradiz o fato de que \(next_j\) é o maior \(x\) satisfazendo a condição. Portanto, tal \(k\) não pode existir.
A ideia central é que \(next_j\) é o maior \(x\), ou seja, não existe um \(x\) maior. Portanto, para provar que não existe tal \(k\), basta mostrar que qualquer \(k\) válido com \(i < k < i'\) implicaria um \(x\) maior, o que contradiz a definição de \(next_j\).
O \(j'\) correspondente pode ser definido como \(j+i-i'\).
Por que exigimos \(next_j = x < j\) ?
Esta pergunta pode parecer óbvia, mas é algo que iniciantes frequentemente perguntam.
Se \(x = j\), obtemos \(i' = j + i - x = i\). Como não existe \(i < k < i'\), a condição é trivialmente satisfeita. Mas como já houve falha em \(i\), tentar corresponder novamente a partir de \(i\) não faz sentido.
Também pode ser entendido assim: \(x = j\) é uma solução trivial que não nos fornece nenhuma "informação", portanto não pode ser usada.
Quando \(next_j = 0\), transferimos para \(i' = i + j\), que corresponde ao caso \(i' > i+j-1\). Como só podemos garantir o intervalo \(i \sim i+j-1\), para satisfazer a condição de que não pode haver correspondência bem-sucedida para \(i < k < i'\), podemos pular no máximo para \(i' = i + j\).
Se considerarmos a complexidade de uma tentativa de correspondência como \(O(1)\), a complexidade de tempo total do algoritmo, em média, é \(O(n+m)\).
Podemos considerar a partir da perspectiva do número de posições que \(i\) e \(j\) pulam. \(i\) aumenta monotonicamente e pode pular no máximo \(n\) vezes. \(j\) só recua em caso de falha, e o número de posições retrocedidas é \(\Delta i = i' - i\), exatamente o número de posições que \(i\) pula diretamente, o que se compensa. Considerando apenas o caso onde \(j\) aumenta, ele pode aumentar no máximo \(m\) vezes. Somando ambos, obtemos a complexidade \(O(m+n)\).
A prova acima também pode ser escrita na forma de análise de potencial, interessados podem tentar por conta própria.
Array next
Calcular o array next pode ser entendido como, para cada prefixo \(S[1, j]\, tentar corresponder com cada \(S[l, j]\ e encontrar o menor \(l > 1\) que satisfaz a condição. No entanto, como precisamos do next para toda \(S\), se calculássemos diretamente de forma ingênua, a complexidade explodiria.
No entanto, como o next para \(S[1, j]\ está relacionado apenas com \(S[1, x] (1 \le x < j)\, podemos considerar calcular de forma recursiva. Em outras palavras, usar as "informações" anteriores.
Pode ser entendido como primeiro "simular uma falha" e depois tentar corresponder consigo mesmo.
O caso limite é \(next_1 = 0\). (Obviamente, \(0 \le next_j < j\), e o único inteiro \(x\) satisfazendo \(0 \le x < 1\) é \(0\))
Suponha que já calculamos \(next_p (1 \le p < i)\, agora vamos calcular \(next_i\).
Pelo exposto, temos \(S[1, next_{i-1}] = S[i-1 - next_{i-1} + 1, i-1]\. Seja \(j = next_{i-1} + 1\, então temos \(S[1, j-1] = S[i-j+1, i-1]\. Desde que \(S_j = S_i\, temos \(S[1, j] = S[i-j+1, i]\, e podemos definir \(next_i \gets j\.
A seguir, provamos a correção por contradição:
Primeiro, como \(next_i\) é o maior possível, temos \(next_i \ge j\). Segundo, não pode haver \(next_i > j\). Se existisse \(x > j\) tal que \(S[1, x] = S[i-x+1, i]\, então teríamos \(S[1, x-1] = S[i-x+1, i-1] (x > j)\, o que contradiz o fato de que já calculamos todos os \(next_p (1 \le p < i)\.
E se \(S_j \ne S_i\?
Pelas propriedades já estabelecidas de next, temos \(S[1, next_{j-1}] = S[j-1 - next_{j-1} + 1, j-1]\. Notando que subseqüências de strings idênticas nas mesmas posições são idênticas. Portanto, \(S[j-1 - next_{j-1} + 1, j-1] = S[i-1 - next_{j-1} + 1, i-1]\. Pela transitividade da relação de equivalência, temos \(S[1, next_{j-1}] = S[i-1 - next_{j-1} + 1, i-1]\. Notamos que agora podemos definir \(j' = next_{j-1} + 1\ e transformar o problema em um subproblema menor.
Na implementação, podemos seguir a forma acima recursivamente, prestando atenção à condição limite \(next_1 = 0\.
Quanto à complexidade de tempo, pode ser provada usando análise de potencial. A ideia geral é definir a função de potencial como o valor atual de \(next_i\. É fácil notar que cada \(i\) pode aumentar no máximo uma vez, e após alguns detalhes, obtemos \(O(m)\), independente do tamanho do conjunto de caracteres. Para mais detalhes, consulte o artigo original mencionado anteriormente.
No entanto, note que esta prova de complexidade de tempo é baseada em média, portanto, o autômato KMP deve incluir o tamanho do conjunto de caracteres para garantir que a complexidade não exceda em outras partes.
[Problema modelo](https://www.luogu.com.cn/record/269618490) ```
#include #include #include using namespace std; vector<size_t> construirNext(const string &padrao) { vector<size_t>resultado(padrao.size(), 0); // next[0] = 0 for(size_t j = 1, k = 0; j < padrao.size(); j++) { while(k && padrao[j] != padrao[k]) k = resultado[k - 1]; if(padrao[j] == padrao[k]) k++; resultado[j] = k; } return resultado; } // Calcula o comprimento do maior prefixo que também é sufixo para S[0, j] vector<size_t> KMP(const string &padrao, const vector<size_t> &prox, const string &texto) { vector<size_t> ocorrencias; size_t i = 0, j = 0; // Começando a correspondência do início if(!(padrao.size() && texto.size())) return ocorrencias; // Caso vazio while(i < texto.size()) { while(j < padrao.size() && i + j < texto.size() && padrao[j] == texto[i + j]) j++; // Até falhar ou corresponder com sucesso // cout << i << ' ' << j <<endl; if(j == padrao.size()) ocorrencias.push_back(i); // Correspondência bem-sucedida if(!(i + j < texto.size())) break; // Texto esgotado // Neste ponto, é necessariamente uma falha ou correspondência bem-sucedida // S[0, j - 1] corresponde a T[i, i + j - 1] size_t novoInicio = (j ? j + i - prox[j - 1]: i + 1); // j = 0 nunca correspondeu if(novoInicio >= i + j) { j = 0; } else { j = i + j - novoInicio; // Próxima posição para tentar correspondência } i = novoInicio; } // i e j são as posições atuais de tentativa de correspondência return ocorrencias; } int main() { string padrao, texto; cin >> texto >> padrao; // Demonstração de implementação com indexação 0 auto nextArray = construirNext(padrao); auto posicoes = KMP(padrao, nextArray, texto); for(auto pos : posicoes) { cout << pos + 1 << endl; } for(auto val : nextArray) { cout << val << " "; } cout << endl; return 0; }
### Border
Ao calcular o array next, só nos preocupamos com o maior \\(x\\) tal que \\(S\[1, x\] = S\[i - x + 1, i\](x < i)\\. Mas como calcular outros \\(x\\) menores?
Por exemplo, em CF2209E A Trivial String Problem, é necessário encontrar para cada prefixo de uma string \\(S\\) o menor \\(x\\) tal que \\(S\[1, x\] = S\[i - x + 1, i\]\\.
Notamos que o array next no KMP tem muitas propriedades interessantes, então vamos discuti-lo separadamente.
Definição: Se uma string \\(K\\) satisfaz \\(K = S\[1, x\] = S\[m - x + 1, m\](x < m)\\, então \\(K\\) é chamada de **border** de \\(S\\).
O nome "border" é bastante intuitivo - se o início e o fim de uma string são idênticos, isso pode ser visto como a "fronteira" da string.
- Lema: Para uma string \\(S\\), a border de uma border ainda é uma border de \\(S\\).
ProvaEsta prova depende principalmente de duas propriedades:
1. A relação de equivalência de strings é transitiva, ou seja, para quaisquer strings \\(A = B\\) e \\(B = C\\), temos \\(A = C\\).
2. Subseqüências de strings idênticas extraídas das mesmas posições são idênticas. Ou seja, se \\(A = B\\), então para qualquer subseqüência válida \\(A\[l,r\]\\, temos \\(A\[l,r\] = B\[l,r\]\\.
Suponha que \\(S\\) tenha uma border \\(S\[1,x\] = S\[m-x+1,m\](x < m)\\. Seja \\(K\\) uma border de \\(S\[1,x\]\\, ou seja, \\(K = S\[1,y\] = S\[x-y+1,x\](y < x)\\. Como \\(S\[x-y+1,x\] = S\[m-y+1,m\]\\, temos \\(K = S\[1,y\] = S\[m-y+1,m\](y < m)\\, ou seja, \\(K\\) é uma border de \\(S\\).
Calcular o array next pode ser visto como uma aplicação da proposição contrapositiva em casos especiais, portanto, o diagrama anterior também pode ajudar a entender.
Seja \\(Border(S) = \\{{border}\_1,{border}\_2,{border}\_3\dots\\}\\, ou seja, \\(Border\\) é uma função que mapeia uma string para o conjunto de todas suas borders. É fácil ver que isso é equivalente a retornar os comprimentos de todas as borders. (Para uma string \\(S\\), uma border de comprimento \\(x\\) é simplesmente \\(S\[1,x\]\\)
Até agora, isso ainda é trivial - apenas definimos formalmente o conceito de border.
Considere alguns conceitos mais complexos.
Vamos pegar uma string aleatória:
`abababbababa`
Suas borders são:
`ababa aba a`
Com um olhar atento, podemos deduzir que para uma border \\(A\\) de \\(S\\), todas as outras borders \\(B\\) de \\(S\\) com comprimento menor que \\(A\\) devem necessariamente ser borders de \\(A\\).
Veja o diagrama abaixo para ajudar a entender.
Como todas as outras borders de \\(S\\) com comprimento menor que \\(K\\) devem ser borders de \\(K\\), para uma string \\(S\\), após encontrar sua maior border \\(K\\, podemos recursivamente encontrar todas as borders de \\(K\\ para obter todas as borders de \\(S\\).
No entanto, às vezes precisamos encontrar borders de prefixos que não são borders da string completa. Nesse caso, podemos usar o array next, tratando o prefixo como uma nova string \\(S'\\ e resolvendo recursivamente.
É fácil notar que a partir de qualquer prefixo de \\(S\\, se continuarmos transferindo para sua maior border, podemos construir uma estrutura em cadeia. Se combinarmos tudo, considerando strings sem border como strings vazias, podemos construir uma árvore com um nó vazio como raiz. Como o array next geralmente é usado em caso de falha, essa árvore também é chamada de árvore de falhas.
\[P5829 【Modelo】Árvore de Falhas\](https://www.luogu.com.cn/record/270237393)```
#include<vector>
#include<iostream>
#include<string>
using namespace std;
const int maxn = 1e6;
vector<size_t> construirNext(const string & s)
{
vector<size_t>ret(s.size(), 0);
// next[0] = 0
for (size_t j = 1, k = 0; j < s.size(); j++)
{
while (k && s[j] != s[k]) k = ret[k - 1];
if (s[j] == s[k]) k++;
ret[j] = k;
}
return ret;
}
// Calcula o comprimento do maior prefixo que também é sufixo para S[0, j]
string s;
int m;
vector<int> filho[maxn + 1];
int pai[maxn + 1], topo[maxn + 1], tamanho[maxn + 1], profundidade[maxn + 1], filhoPrincipal[maxn + 1];
void dfs1(int u)
{
tamanho[u] = 1;
filhoPrincipal[u] = 0;
for (int v : filho[u])
{
if (v == pai[u]) continue;
profundidade[v] = profundidade[pai[v] = u] + 1;
dfs1(v);
tamanho[u] += tamanho[v];
if (!filhoPrincipal[u] || tamanho[filhoPrincipal[u]] < tamanho[v]) filhoPrincipal[u] = v;
}
}
void dfs2(int u)
{
if (filhoPrincipal[u])
{
topo[filhoPrincipal[u]] = topo[u];
dfs2(filhoPrincipal[u]);
}
// Processa filho principal primeiro
for (int v : filho[u])
{
if (v == pai[u]) continue;
if (v == filhoPrincipal[u]) continue;
topo[v] = v;
dfs2(v);
}
}
int lca(int x, int y)
{
while (topo[x] != topo[y])
{
if (profundidade[topo[x]] < profundidade[topo[y]]) swap(x, y);
x = pai[topo[x]];
}
if (profundidade[x] < profundidade[y]) swap(x, y);
return y;
// y tem profundidade menor
}
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cin >> s >> m;
auto prox = construirNext(s);
for (size_t i = 0; i < prox.size(); i++)
{
filho[prox[i]].push_back(i + 1);
}
profundidade[0] = 0;
pai[0] = 0;
topo[0] = 0;
dfs1(0);
dfs2(0);
for (int i = 1, p, q; i <= m; i++)
{
cin >> p >> q;
int lca_pq = lca(p, q);
if (lca_pq == p || lca_pq == q) lca_pq = pai[lca_pq];
cout << lca_pq << endl;
}
return 0;
}
Problema não-modelo: "Pequenos Problemas Incríveis - Verificando Strings b"
Tarefa Final
Ótimo, agora você aprendeu KMP.
Agora, desafie-se a resolver P15650 [Seletivo Conjugado 2026] String Mocha / string!
Últimas palavras (?)
O autor é um iniciante e ainda não ousa dizer que consegue resolver a maioria dos problemas de strings. A razão principal é que minha compreensão de strings era muito superficial, e mantive uma "arrogância" em relação aos algoritmos "básicos". Essa "arrogância" é semelhante, mas diferente da "arrogância do estilo CleanIce" - não é a arrogância de profissionais do mundo real em relação a OIers que fazem pesquisa teórica de algoritmos, mas sim a arrogância de OIers que se consideram dominam muitos algoritoms avançados em relação a algoritmos "básicos". Como o autor ainda não encontrou ninguém que tenha proposto isso antes, seguindo a convenção acadêmica, vou chamá-la de "arrogância do estilo clx201022".Se outras pessoas já propuseram isso, por favor, não me culpem.
- Análise do humor: Ao escrever este parágrafo, o autor várias vezes escreveu "arrogância" como "amao".
Links Relacionados
- Notas de estudo sobre hash de strings
- Strings - Notas de estudo - Explicação de algoritmos 1
- "Pequenas Notas sobre Teoria de Border", @command_block
- Os diagramas foram criados usando um quadro de rascunho online.
Declaração de Autoria
Este artigo segue a licença CC BY-SA 4.0.
Garanto que este artigo não foi criado com a ajuda de ferramentas de IA.
- Ou seja, strings. ↩︎
- Formação (yi) nível, situação alcançado em estudos acadêmicos, técnicas especializadas; visitar. ↩︎
- Primeiro a sofrer ataque ou primeiro a encontrar desastre. ↩︎
- Mais sobre relações de ordem parcial e total. ↩︎
- Onde \(s[l, r]\) é trivial, representando \(s_l s_{l+1}\dots s_{r-1}s_r\). ↩︎
- Não é este "não é". ↩︎