Eu preciso comparar as strings para decidir se elas representam a mesma coisa. Isso se relaciona com os títulos de casos inseridos por seres humanos, onde as abreviações e outros pequenos detalhes podem ser diferentes. Por exemplo, considere os dois títulos a seguir:

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";

Ao contrário de:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";

Um ser humano pode avaliar rapidamente que são provavelmente o mesmo. A abordagem atual que tomei é normalizar as strings diminuindo todas as letras e removendo todas as pontuações e espaços que dão:

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";

E:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp";

Comparando, neste caso, uma é uma sub-seqüência da outra, mas você pode imaginar outras variações mais complexas onde isso não necessariamente ocorre, ainda que elas tenham sub-sequências significativas em comum. Também pode haver erros ocasionais de entrada humana, como letras transpostas e erros de ortografia.

Talvez algum tipo de programa de diferenciação de personagens possa ajudar? Eu vi bons programas de comparação de linhas para comparar as diferenças no código a serem verificadas, há algo assim em caráter, talvez em aumento? Se você pudesse contar o número de caracteres consecutivos em comum e levar a proporção para os personagens não compartilhados, talvez isso seria uma boa heurística?

No final, preciso de uma decisão booleana para considerá-los iguais ou não. Não precisa ser perfeito, mas, idealmente, raramente deveria estar errado.

Que algoritmo posso usar que me dará algum tipo de quantificação de como as duas seqüências são semelhantes umas às outras que eu posso então converter em uma resposta sim / não por meio de alguma heurística?