Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
stuxjkee
0 / 0 / 0
Регистрация: 18.04.2014
Сообщений: 15
#1

Сделать из строки A строку B - C++

01.05.2014, 17:35. Просмотров 222. Ответов 5
Метки нет (Все метки)

Какое наименьшее количество операций(добавить 1 символ, удалить 1 символ, заменить 1 символ) нужно сделать, чтобы из строки A получить строку B?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2014, 17:35     Сделать из строки A строку B
Посмотрите здесь:

C++ нужно сделать бугущую строку, помогите пожалуйста!!
C++ Выяснить, можно ли из строки st1 сделать строку st2 путем перестановки символов
C++ Как сделать ввод в одну строку?
Заменить все вхождения строки s2 в строку s1 на строку s3 C++
C++ Подключить строку cmd и сделать запрос ping
Преобразование строки в строку? C++
Сделать два массива в две строки и вывести результат сложения их в третью строку C++
Копирование строки в строку C++
C++ Как сделать из #define строку?
Программа считывает только первую строку файла,как сделать чтобы она считывала все строки C++
C++ Из строки сформировать отдельно строку латинских и строку русских букв
Как сделать проверку перехода на новую строку? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
4921 / 4259 / 1426
Регистрация: 14.04.2014
Сообщений: 16,745
01.05.2014, 17:37     Сделать из строки A строку B #2
Сколько символов в самой длинной строке, столько и операций.
cooller
564 / 532 / 120
Регистрация: 25.12.2013
Сообщений: 1,456
01.05.2014, 17:39     Сделать из строки A строку B #3
Цитата Сообщение от nmcf Посмотреть сообщение
Сколько символов в самой длинной строке, столько и операций.
наименьшее! если есть повторяющиеся символы, то не нужно их заменять, имхо
Somebody
2778 / 1592 / 142
Регистрация: 03.12.2007
Сообщений: 4,175
Завершенные тесты: 1
01.05.2014, 17:51     Сделать из строки A строку B #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Расстояние Левенштейна
nmcf
4921 / 4259 / 1426
Регистрация: 14.04.2014
Сообщений: 16,745
01.05.2014, 18:17     Сделать из строки A строку B #5
А сравнить символ не считается?
stuxjkee
0 / 0 / 0
Регистрация: 18.04.2014
Сообщений: 15
01.05.2014, 18:29  [ТС]     Сделать из строки A строку B #6
Цитата Сообщение от Somebody Посмотреть сообщение
Расстояние Левенштейна
Спасибо. Вот код, если кому-то интересно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <string>
 
using namespace std;
 
int dis(string a, string b)
{
    int m = a.length();
    int n = b.length();
    int len[10001][10001];
    for (int i = 0; i <=m; i++)
        len[i][0] = i;
    for (int j = 0; j <= n; j++)
        len[0][j] = j;
 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
        {
            if (a[i] == b[j])
                len[i+1][j+1]=len[i][j];
            else
                len[i+1][j+1] = 1 + min(len[i][j], min(len[i+1][j], len[i][j+1]));
 
        }
    return len[m][n];
}
 
int main()
{
    string a,b;
    cin >> a >> b;
    cout << dis(a,b) << endl;
    //system("pause");
}
Yandex
Объявления
01.05.2014, 18:29     Сделать из строки A строку B
Ответ Создать тему
Опции темы

Текущее время: 18:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru