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

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

Восстановить пароль Регистрация
 
stuxjkee
0 / 0 / 0
Регистрация: 18.04.2014
Сообщений: 15
01.05.2014, 17:35     Сделать из строки A строку B #1
Какое наименьшее количество операций(добавить 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 путем перестановки символов
Заменить все вхождения строки s2 в строку s1 на строку s3 C++
C++ Дан символ C и строки S, S0. После каждого вхождения символа C в строку S вставить строку S0
Ввести строку, создать вторую строку в два раза больше, в которую записать симболы первой строки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
01.05.2014, 17:37     Сделать из строки A строку B #2
Сколько символов в самой длинной строке, столько и операций.
cooller
 Аватар для cooller
564 / 532 / 120
Регистрация: 25.12.2013
Сообщений: 1,456
01.05.2014, 17:39     Сделать из строки A строку B #3
Цитата Сообщение от nmcf Посмотреть сообщение
Сколько символов в самой длинной строке, столько и операций.
наименьшее! если есть повторяющиеся символы, то не нужно их заменять, имхо
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
01.05.2014, 17:51     Сделать из строки A строку B #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Расстояние Левенштейна
nmcf
4297 / 3718 / 1251
Регистрация: 14.04.2014
Сообщений: 14,540
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
Ответ Создать тему
Опции темы

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