#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;
}
Проверка слов на анаграммы [C++(Dos)]
Дана строка, содержащая текст. Найти слова в тексте, которые можно составить из первого и последнего слова (буквы можно использовать не более одного раза)
Подскажите как по символьно сравнить слова, а то я даже не знаю с чего начать.
Заранее благодарю
Ну, например, можно отсортировать буквы обоих слов по алфавиту и потом сравнить.
Код:
Требования (в этой версии) к текстовой строке: только прописные буквы, не должна заканчиваться пробелом, никаких знаков препинания и т.п. Это уже для самостоятельной работы...
P.S. Потестил чуток, вроде работает... а так смотри, исправляй. Очень многое переделать можно (и нужно), но... ;)
И на этом спасибо, теперь хоть есть информация к размышлению :)
Код:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
void main(void)
{
char src[] = "abcdf gjhgjk abq pfca pafd";//если в строке будет меньше двух слов - будет исключение вылетать áóäåò âûëåòàòü 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);
}
}
}
#include <ctype.h>
#include <string.h>
void main(void)
{
char src[] = "abcdf gjhgjk abq pfca pafd";//если в строке будет меньше двух слов - будет исключение вылетать áóäåò âûëåòàòü 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);
}
}
}
Цитата: OlgaKr
вот тебе еще пища для размышления, но логика очень простая и на С
Код:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
void main(void)
{
char src[] = "abcdf gjhgjk abq pfca pafd";//если в строке будет меньше двух слов - будет исключение вылетать áóäåò âûëåòàòü exception
int lexicon[26] = {0};
int temp[26] = {0};
int i, j;
char *ptr, *p;
//.................................
#include <ctype.h>
#include <string.h>
void main(void)
{
char src[] = "abcdf gjhgjk abq pfca pafd";//если в строке будет меньше двух слов - будет исключение вылетать áóäåò âûëåòàòü exception
int lexicon[26] = {0};
int temp[26] = {0};
int i, j;
char *ptr, *p;
//.................................
этот код работает только с английским символами, а как сделать что бы он и русские символы тоже понимал ?
Цитата:
этот код работает только с английским символами, а как сделать что бы он и русские символы тоже понимал ?
я не знаю как с русским работать.
но вообщем так, тож пища для размышленний =), на случай если решишь развить тему анаграм.
Встречал я про аннаграмы в книжке "Жемчужины программирования" (автора уже не помню). Анаграмы там искались следующим образом. Каждому слову в соответсвие ставилось другое слово состоящие из букв искомого слова, упорядоченных в алфавитном порядке и цифр перед каждой буквой, определющих количество повторений буквы в слове. Пример СКОС - КО2С. Таким образом для
слов СКОС и СОКС - генерировалось строка КО2С, по которой и определялось наличие анаграмы. В программе словарь упорядочивался по генерируемым строкам, что в дальнейшем позволяло использовать двоичный поиск.