Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Проверка слов на анаграммы [C++(Dos)]

23K
18 мая 2007 года
S!nner
10 / / 16.05.2007
Вообщем задача такая:

Дана строка, содержащая текст. Найти слова в тексте, которые можно составить из первого и последнего слова (буквы можно использовать не более одного раза)

Подскажите как по символьно сравнить слова, а то я даже не знаю с чего начать.
Заранее благодарю
247
19 мая 2007 года
wanja
1.2K / / 03.02.2003
Ну, например, можно отсортировать буквы обоих слов по алфавиту и потом сравнить.
9
20 мая 2007 года
Lerkin
3.0K / / 25.03.2003
Если я правильно понял, то вот что у меня получилось:
Код:
#include <iostream>
using namespace std;

#include <stdlib.h>
#include <string.h>

#define BUFF_SIZE   64
[COLOR="SeaGreen"]
// создание словаря из первого и последнего слова[/COLOR]
void make_dictionary( char* str, char* dict )
{
    char* p = str;

    [COLOR="SeaGreen"]// получить первое слово[/COLOR]
    while (*p != ' ')
    *dict++ = *p++;

    [COLOR="SeaGreen"]// получить последнее слово[/COLOR]
    while (*p)
    if (*p++ == ' ')
        str = p;

    while (*dict++ = *str++);
}

[COLOR="SeaGreen"]// поиск анаграмм[/COLOR]
int search_anagram( char* word_buffer, char* dict )
{
    [COLOR="SeaGreen"]// временный словарь[/COLOR]
    char tmp_dict[BUFF_SIZE];
    strcpy( tmp_dict, dict );

    [COLOR="SeaGreen"]// цикл проверки по словарю[/COLOR]
    int check_size = 0;
    int word_pos = strlen( word_buffer );

    while (word_pos--)
    {
    char* p = tmp_dict;

    do
    {
        if (*p == word_buffer[word_pos])
        {
        [COLOR="SeaGreen"]// чтобы не было повторений, удаляем[/COLOR]
        [COLOR="SeaGreen"]// использованную букву из словаря[/COLOR]
        *p = '.';

        check_size++;
        break;
        }
    }
    while (*p++);

    [COLOR="SeaGreen"]// если какой-то буквы слова нет в словаре,[/COLOR]
    [COLOR="SeaGreen"]// проверять остальное не имеет смысла[/COLOR]
    if (!*(--p))
        break;
    }

    return check_size;
}

[COLOR="SeaGreen"]// разбор строки[/COLOR]
void out_words( char* str, char* dict)
{
    [COLOR="SeaGreen"]// определить границы слов в строке[/COLOR]
    [COLOR="SeaGreen"]// т.е. проверять все слова, кроме первого и последнего[/COLOR]
    char* begin = str, *end;

    while (*begin++ != ' ');
    while (*str++)
    if (*str == ' ')
        end = ++str;

    [COLOR="SeaGreen"]// основной цикл[/COLOR]
    const char* p = begin;
    int dict_length = strlen( dict );

    while (p != end)
    {
    [COLOR="SeaGreen"]// буфер для сравниваемого слова и его размер[/COLOR]
    char word_buffer[BUFF_SIZE];
    int word_buffer_size = 0;

    [COLOR="SeaGreen"]// получить следующее слово из строки[/COLOR]
    while ((word_buffer[word_buffer_size++] = *p++) != ' ');
    word_buffer[--word_buffer_size] = '\0';

    [COLOR="SeaGreen"]// если размер слова больше чем словарь, его не проверяем[/COLOR]
    if (word_buffer_size <= dict_length)
        if (word_buffer_size == search_anagram( word_buffer, dict ))
        cout << word_buffer << endl;

    p++;
    }
}

int main(int argc, char* argv[])
{
    [COLOR="SeaGreen"]// строка текста. первый и последний символы НЕ должны быть пробелами![/COLOR]
    char* str = "...текстовая строка...";

    [COLOR="SeaGreen"]// словарь (первое и последнее слово)[/COLOR]
    char dict[BUFF_SIZE];
    make_dictionary( str, dict );

    [COLOR="SeaGreen"]// основная функция[/COLOR]
    out_words( str, dict );

    return 0;
}

Требования (в этой версии) к текстовой строке: только прописные буквы, не должна заканчиваться пробелом, никаких знаков препинания и т.п. Это уже для самостоятельной работы...

P.S. Потестил чуток, вроде работает... а так смотри, исправляй. Очень многое переделать можно (и нужно), но... ;)
23K
20 мая 2007 года
S!nner
10 / / 16.05.2007
И на этом спасибо, теперь хоть есть информация к размышлению :)
242
20 мая 2007 года
Оlga
2.2K / / 04.02.2006
вот тебе еще пища для размышления, но логика очень простая и на С
Код:
#include <stdio.h>
#include <ctype.h>
#include <string.h>

void main(void)
{
    char src[] = "abcdf gjhgjk  abq pfca pafd";//если в строке будет меньше двух слов - будет исключение вылетать  &#225;&#243;&#228;&#229;&#242; &#226;&#251;&#235;&#229;&#242;&#224;&#242;&#252; exception
    int lexicon[26] = {0};
    int temp[26] = {0};
    int i, j;
    char *ptr, *p;

    /*** состовляем словарь символов***/
    i = (strlen(src)-1);

    while(i >= 0 && src != ' ') // && !ispunct(src)
    {
        lexicon[src-'a']++;
        src = 0;
        --i;
    }

    ptr = strtok(src, " ,.!?");
    while(*ptr)
    {
        lexicon[*ptr-'a']++;
        ptr++;
    }

    /***  проверяем слова  ***/
    while(ptr)
    {
       
        if((ptr = strtok(0, " ,.!?"))!=0)
        {
            for( i = 0; i < 26; ++i)
                temp = 0;
           
            p = ptr;

            while(*p)
            {
                temp[*p-'a']++;
                p++;
            }

            for(i = 0; i < 26; i++)
                if(temp > lexicon)
                    break;
            if(i == 26)
                printf("%s\n", ptr);
        }
           
    }
}
23K
21 мая 2007 года
S!nner
10 / / 16.05.2007
Цитата: OlgaKr
вот тебе еще пища для размышления, но логика очень простая и на С
Код:
#include <stdio.h>
#include <ctype.h>
#include <string.h>

void main(void)
{
    char src[] = "abcdf gjhgjk  abq pfca pafd";//если в строке будет меньше двух слов - будет исключение вылетать  &#225;&#243;&#228;&#229;&#242; &#226;&#251;&#235;&#229;&#242;&#224;&#242;&#252; exception
    int lexicon[26] = {0};
    int temp[26] = {0};
    int i, j;
    char *ptr, *p;
    //.................................



этот код работает только с английским символами, а как сделать что бы он и русские символы тоже понимал ?

242
21 мая 2007 года
Оlga
2.2K / / 04.02.2006
Цитата:
этот код работает только с английским символами, а как сделать что бы он и русские символы тоже понимал ?



я не знаю как с русским работать.

361
21 мая 2007 года
Odissey_
661 / / 19.09.2006
Незнаю, скажу ли я что новое...
но вообщем так, тож пища для размышленний =), на случай если решишь развить тему анаграм.

Встречал я про аннаграмы в книжке "Жемчужины программирования" (автора уже не помню). Анаграмы там искались следующим образом. Каждому слову в соответсвие ставилось другое слово состоящие из букв искомого слова, упорядоченных в алфавитном порядке и цифр перед каждой буквой, определющих количество повторений буквы в слове. Пример СКОС - КО2С. Таким образом для
слов СКОС и СОКС - генерировалось строка КО2С, по которой и определялось наличие анаграмы. В программе словарь упорядочивался по генерируемым строкам, что в дальнейшем позволяло использовать двоичный поиск.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог