algo para encontrar o número de caracteres comuns em 2 seqüências de caracteres [duplicados] - c, string, algoritmo

Estou escrevendo um programa c para encontrar o número de caracteres comuns em duas strings.

Por exemplo: aabbccc aabc Resp: 4

   aabcA     aa       Ans:2

(As strings terão maiúsculas, minúsculas e números)

Eu tenho dois algoritmos em minha mente

Assumindo que o comprimento das strings é n, m

1.Ordenar as matrizes e contar a complexidade de O (nlogn + mlogm)

2. digitalize através de duas strings e use matrizes de contagem - complexidade O (n + m)

Alguém pode sugerir mais otimização ou quaisquer outros métodos para fazer isso?

Respostas:

basicamente você está perguntando sobre um Interseção de sacos (multiset).

e acho que não haverá algo mais eficiente que O (n + m) porque você terá que passar por cada elemento de duas malas pelo menos uma vez.

Desde que, a otimização é necessária para grande entrada, euacho que seu segundo método é muito bom (método de contagem de array). Qualquer que seja o algoritmo que você tenta descobrir, não consegue encontrar a resposta para o seu problema sem examinar as duas seqüências completamente. Portanto, não deve haver mais otimização para esse problema, pois ele já é O (m + n). Eu acho que para entradas menores, seu primeiro algoritmo funcionará mais rápido, pois há uma constante de O (26 + 26 + 10) associada ao seu segundo algoritmo. Mas se você estiver realmente interessado em um código mais rápido, tente otimizar o método de leitura e gravação da saída. Você pode procurar no Google por "E / S mais rápida em C ++" e ler sobre isso.