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

Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
31.08.2010, 20:32     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #1
нужно найти в строке пару символов, которые повторяются чаще всех и заменить их на один новый символ например acfghhachfjiac "ac" заменить на "X" и чтобы в итоге вышло XfghhXhfjiX

как считать строку из файла в стринг, если она содержит пробелы (нужно считать из файла строку с пробелами)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.08.2010, 20:32     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ
Посмотрите здесь:

Сформировать список символов, оканчивающийся точкой. Заменить в списке символ “A” на символ “0” C++
C++ [C++] в строке символов заменить каждый второй символ s на f
Найти слово, в котором заданный символ встречается наиболее часто C++
C++ Наиболее часто встречающийся символ в текстовом файле
Найти слова где заданный символ встречаются наиболее часто C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
31.08.2010, 20:39     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #2
Mayonez, 2
C++
1
std::getline(имя потока, имя строки);
rrrFer
Заблокирован
31.08.2010, 20:45     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <fstream>
using std::ifstream;
#include <string>
using std::string;
 
int main(){
    string s;
    ifstream f;
 
    f.open("in.txt");
    if(!f)
        return 1;
 
    while(!f.eof())
        s+=f.get();
 
    return 0;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 20:48     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #4
Mayonez,
Навскидку, первое, что пришло в голову... Проходя по строке в первый раз, создать таблицу уникальных пар (т.е. в строке acfghhachfjiac уникальными парами будут ac, cf, fg, gh, hh, ha, ch, hf, fj, ji и ia). Затем для каждой пары поставить в соответствие количество раз, которое она встречается в строке (для каждой пары делаем проход по строке и считаем количество совпадений). Ну а затем в новый массив переписываем входную строку, постоянно отслеживая пару, повторяющуюся максимальное число раз, и при переписывании заменяем её на требуемый символ...

Кстати, первый и второй пункты можно объединить (видим пару - проверяем, нет ли её в таблице, если нет - добавляем, а если нашли, тут же увеличиваем её счётчик и переходим к следующей паре).
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
31.08.2010, 21:50  [ТС]     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #5
Цитата Сообщение от silent_1991 Посмотреть сообщение
Mayonez,
Навскидку, первое, что пришло в голову... Проходя по строке в первый раз, создать таблицу уникальных пар (т.е. в строке acfghhachfjiac уникальными парами будут ac, cf, fg, gh, hh, ha, ch, hf, fj, ji и ia). Затем для каждой пары поставить в соответствие количество раз, которое она встречается в строке (для каждой пары делаем проход по строке и считаем количество совпадений). Ну а затем в новый массив переписываем входную строку, постоянно отслеживая пару, повторяющуюся максимальное число раз, и при переписывании заменяем её на требуемый символ...

Кстати, первый и второй пункты можно объединить (видим пару - проверяем, нет ли её в таблице, если нет - добавляем, а если нашли, тут же увеличиваем её счётчик и переходим к следующей паре).
это я понимаю, но реализовать как-то не получается
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 21:57     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #6
Mayonez,
Почти дописал))) Правда на Си будет, ну и с файлами я не стал заморачиваться, сделал ввод с клавиатуры, так что тебе останется только ввод-вывод переделать.

Добавлено через 5 минут
Кстати, а если несколько пар повторяются одинаковое число раз, и это как раз максимальное число повторений, как тогда поступить?
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
31.08.2010, 22:08  [ТС]     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #7
заменить или любую из пар или обе но на две разные буквы
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 22:09     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #8
Т.е. возможно любое решение? Разрешите, я остановлюсь на первом, когда выложу код, скажу идеи, как его можно переделать под второй вариант...
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
31.08.2010, 22:11  [ТС]     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #9
окей, давай
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.08.2010, 22:48     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #10
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
struct pair
{
    char p[2];
    int counter;
    struct pair *next;
};
 
struct pair *search(struct pair *start, char *need);
void max(struct pair *start, char *need);
struct pair *unique(char *str);
void exchange(struct pair *first, char ch, char *instr, char *outstr);
 
struct pair *search(struct pair *start, char *need)
{
    while (start)
    {
        if (start->p[0] == need[0] && start->p[1] == need[1])
            return start;
 
        start = start->next;
    }
 
    return NULL;
}
 
void max(struct pair *start, char *need)
{
    int max;
    
    max = start->counter;
    need[0] = start->p[0];
    need[1] = start->p[1];
    
    while (start)
    {
        if (start->counter > max)
        {
            max = start->counter;
            need[0] = start->p[0];
            need[1] = start->p[1];
        }
 
        start = start->next;
    }
}
 
struct pair *unique(char *str)
{
    struct pair *first, *last, *node;
    char temp[2];
    int i;
    
    first = (struct pair *)malloc(sizeof(struct pair));
    first->p[0] = str[0];
    first->p[1] = str[1];
    first->counter = 1;
    first->next = NULL;
    node = first;
    last = first;
    
    for (i = 1; i < strlen(str) - 1; i++)
    {
        temp[0] = str[i];
        temp[1] = str[i + 1];
        node = search(first, temp);
        
        if (!node)
        {
            node = (struct pair *)malloc(sizeof(struct pair));
            node->p[0] = temp[0];
            node->p[1] = temp[1];
            node->counter = 1;
            last->next = node;
            node->next = NULL;
            last = node;
        }
        else
        {
            node->counter++;
        }
    }
    
    return first;
}
 
void exchange(struct pair *first, char ch, char *instr, char *outstr)
{
    char need[2];
    int i, j;
    
    max(first, need);
    
    for (i = 0, j = 0; i <= strlen(instr); i++)
    {
        if (instr[i] == need[0] && instr[i + 1] == need[1])
        {
            outstr[j++] = ch;
            i++;
        }
        else
        {
            outstr[j++] = instr[i];
        }
    }
}
 
int main()
{
    char instr[40];
    char outstr[40];
    char c;
    struct pair *p;
    
    printf("Vvedite stroku: ");
    scanf("%s", instr);
    printf("Vvedite simvol: ");
    scanf("%s", &c);
    p = unique(instr);
    exchange(p, c, instr, outstr);
    printf("Rezultat: %s", outstr);
    
    getch();
    return 0;
}
Добавлено через 7 минут
Для, того, чтобы заменять другие пары, нужно сохранить найденное в первый раз максимальное число повторений, затем, после того, как произошла первая замена, входной строкой мы делаем получившуюся выходную (в которой один вид пар уже заменён некоторым символом), а из списка пар удаляем элемент, соответствующий заменяемой только что паре. Далее ищем в списке элемент, значение counter которого совпадает с ранее найденным максимальным значением (его менять больше не будем), и производим замену в строке уже этой пары. И это всё проделываем в цикле, пока есть элементы списка, значение counter которых совпадает с найденным в самый первый раз максимальным значением.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
01.09.2010, 15:57  [ТС]     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #11
вот что получилось у меня на с+++STL
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
//поиск и замена
string search(string s);
string replace(string what, string slov);
 
int main()
{
   string s;
   cin>>s;
   //если найдены пары, которые повторяются, то
   while(search(s)!="")
   //заменяем их на новый символ
      s=replace(search(s), s);
      
   //что получилось в конце
   cout<<s<<endl;
   return 0;
}
 
string search(string s)
{
   vector<int> max(s.size(), 1);
   int result, back=0;
   for(int i=0; i<s.size(); i++)
      for(int j=0; j<s.size(); j++)
      {
         if(j==i || j+1==i) {j+=2; continue;}
         if(s[j]==s[i] && s[j+1]==s[i+1]) max[i]++;
      }
   result=max[0];
   for(int i=0; i<max.size()-1; i++)
      if(max[i]>result) {result=max[i]; back=i;}
   string zam;
   string no="";
   zam+=s[back];
   zam+=s[back+1];
   if(result==1) return no;
   return zam;
}
 
string replace(string what, string slov)
{
   string result;
   static char simvol=128;
   for(int i=0; i<slov.size()-1; i++)
   {
      if(what[0]==slov[i] && what[1]==slov[i+1])
      {
         result+=simvol;
         i++;
      }
      else 
      result+=slov[i];
   }
   simvol++;
   return result;
}
у меня заменяет абсолютно все пары, которые повторяются
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
01.09.2010, 17:45     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #12
А вот что у меня получилось C++ + STL:
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
37
#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
#include <algorithm>
 
bool compareMap(const std::pair<std::string, size_t>& a,
                const std::pair<std::string, size_t>& b)
{
    return a.second < b.second;
}
 
int main()
{
    std::string str;
    std::map<std::string, size_t> pairs;
    std::cout << "Input the string to proccess: ";
    std::getline(std::cin, str);
    char c;
    std::cout << "Input the character to replace: ";
    std::cin >> c;
    size_t index = 0;
    while(index != str.size() - 2)
    {
        std::string pair = str.substr(index++, 2);
        if(pair.find(' ') == std::string::npos)
            ++pairs[pair];
    }
    std::map<std::string, size_t>::const_iterator it =
            std::max_element(pairs.begin(), pairs.end(), compareMap);
    std::cout << "Replacing \'" << it->first << "\' with \'" << c << "\'..."
            << std::endl;
    while((index = str.find(it->first)) != std::string::npos)
        str.replace(index, 2, 1, c);
    std::cout << "Proccessed string: \'" << str << "\'" << std::endl;
    return EXIT_SUCCESS;
}
punhin
0 / 0 / 0
Регистрация: 30.08.2010
Сообщений: 12
02.09.2010, 10:06     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #13
Цитата Сообщение от Mayonez Посмотреть сообщение
заменить или любую из пар или обе но на две разные буквы
нда... интересно, как это (замена на две разные буквы) получится с последовательностью ababababababab (ab и ba встречаются одинаково часто)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
02.09.2010, 10:09     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #14
Банально - первая найденная пара - ab - будет первой в списке уникальных. При поиске пар с максимальной повторяемостью она также всплывёт первой - её-то и будем заменять... А то, что есть ещё и ba, мы и не узнаем потом, да и это нюансы, которые обычно решаются так, как я и описал выше, по принципу "кто первый встал - того и тапки"...
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
02.09.2010, 10:13     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #15
Цитата Сообщение от punhin Посмотреть сообщение
ababababababab (ab и ba встречаются одинаково часто)
Как так - одинаково? ab встречается 7 раз, ba - 6.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
02.09.2010, 10:14     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #16
abababababababa
А так?
Nameless One
02.09.2010, 10:38
  #17

Не по теме:

silent_1991, тут ты меня и подловил

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2010, 14:50     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ
Еще ссылки по теме:

строки:заменить каждый символ '/' на пару символов ': ' C++
C++ Заменить все(один) символ(ы) в Unicode строке
C++ Поиск наиболее часто встречающейся подстроки в строке

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

Или воспользуйтесь поиском по форуму:
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
03.09.2010, 14:50  [ТС]     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ #18
Цитата Сообщение от punhin Посмотреть сообщение
нда... интересно, как это (замена на две разные буквы) получится с последовательностью ababababababab (ab и ba встречаются одинаково часто)
скомпилируй програму из моего кода и увидишь...
Yandex
Объявления
03.09.2010, 14:50     Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ
Ответ Создать тему
Опции темы

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