algo, щоб знайти кількість загальних символів у 2 рядках [дублікат] - c, рядок, алгоритм

Я пишу програму c, щоб знайти кількість загальних символів у двох рядках.

Наприклад: aabbccc aabc Відповідь: 4

   aabcA     aa       Ans:2

(У рядків буде верхній регістр, нижній регістр та цифри)

У мене на увазі два алгоритми

Припускаючи, що довжина струн дорівнює n, м

1. Сортувати масиви, а потім порахувати складність O (nlogn + mlogm)

2.можна пройти через два рядки і використовувати масиви підрахунку - складність O (n + m)

Чи може хто-небудь запропонувати подальшу оптимізацію чи будь-які інші методи для цього?

Відповіді:

в основному ви запитуєте про Перехрестя сумки (мультисети).

і я здогадуюсь, що не вийде більш ефективного альго, ніж O (n + m), тому що вам доведеться хоча б один раз пройти кожен елемент двох мішків.

Оскільки для великого вкладу потрібна оптимізаціядумаю, ваш другий метод досить чудовий (метод підрахунку масиву). Який би алгоритм ви не намагалися з’ясувати, ви не можете знайти відповідь на свою проблему, не переглядаючи ці два рядки повністю. Отже, не повинно бути жодної подальшої оптимізації цієї проблеми, оскільки вона вже є O (m + n). Я думаю, що для меншого введення ваш перший алгоритм буде працювати швидше, оскільки є константа O (26 + 26 + 10), пов'язана з вашим другим алгоритмом. Але якщо вас дійсно цікавить більш швидкий код, то спробуйте оптимізувати метод читання та запису виводу. Ви можете google для "швидшого вводу / виводу в C ++" і прочитати про нього.