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

Является ли первая строка циклическим сдвигом второй строки - C++

Восстановить пароль Регистрация
 
Sarmat
 Аватар для Sarmat
3 / 3 / 1
Регистрация: 13.11.2010
Сообщений: 57
03.11.2011, 18:33     Является ли первая строка циклическим сдвигом второй строки #1
Привет всем. Помогите пожалуйста написать код: нужно проверить, есть ли первая строка (с клавиатуры) циклическим сдвигом второй строки (тоже с клавиатуры).
Зарание всем спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2011, 18:33     Является ли первая строка циклическим сдвигом второй строки
Посмотрите здесь:

Расшифровка строки (циклическим сдвигом букв латинского алфавита на n символов) C++
Ввести две символьных строки. Выполнить поиск второй строки в первой и вывести номер позиции, с которой вторая строка содержится в первой. C++
Строка: Определить местоположение символа первой строки,который первым совпал с одним из символов второй строки. C++
Строка: Определить местоположение символа первой строки,который первым совпал с одним из символов второй строки. C++
C++ Строка: Определите длину введенной строки, и если она кратна 4, то поменяйте местами первую часть строки со второй
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
03.11.2011, 19:19     Является ли первая строка циклическим сдвигом второй строки #2
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
#include <stdio.h>
 
int isshift(char *, char *);
char *remove_nl(char *);
 
#define MAXLINE 1000
 
int main()
{
    char line[MAXLINE], line1[MAXLINE];
 
    while (printf("enter a first line: ") && *fgets(line, MAXLINE, stdin) != '\n') {
        printf("enter a second line: ");
        fgets(line1, MAXLINE, stdin);
        printf("the first line is %sa cyclic shift of the second\n",
            isshift(remove_nl(line), remove_nl(line1)) ? "" : "NOT ");
    }
    return 0;
}
 
 
#include <string.h>
 
char *remove_nl(char *s)
{
    char *p;
 
    if ((p = strrchr(s, '\n')) != NULL)
        *p = '\0';
    return s;
}
 
char *shift(char *);
 
int isshift(char *s, char *t)
{
    int i, slen = strlen(s);
 
    if (slen != strlen(t))
        return 0;
    for (i = 0; i < slen; i++)
        if (!strcmp(shift(s), t))
            return 1;
    return 0;
}
 
char *shift(char *s)
{
    char c, *beg = s;
 
    if ((c = *s) == '\0')
        return beg;
    for (s++; *s != '\0'; s++)
        *(s - 1) = *s;
    *(s - 1) = c;
    return beg;
}
Добавлено через 4 минуты
альтернативный цикл while
C
1
2
3
4
5
    while (printf("enter a first line: ") && *fgets(line, MAXLINE, stdin) != '\n'
        && printf("enter a second line: ") && fgets(line1, MAXLINE, stdin)
        && printf("the first line is %sa cyclic shift of the second\n",
            isshift(remove_nl(line), remove_nl(line1)) ? "" : "NOT "))
        ;
TwiX
59 / 59 / 1
Регистрация: 27.10.2011
Сообщений: 189
03.11.2011, 20:52     Является ли первая строка циклическим сдвигом второй строки #3
Вот более интеллектуальный метод Вероятно, существуют такие строки, для которых он не даст точного ответа (поэтому прога и выводит, что строки ВЕРОЯТНО являются соседними). Это что-то вроде характеристической функции, которая будет работать в разы быстрее полного алгоритма. Т.е. если надо сравнивать кучу строк, то лучше будет сначала вбивать их в мой алгоритм, а потом (если он сказал, что они похожи), то полный алгоритм.
П.с. Заведемо известно, что строки одинаковой длины - лень было проверку делать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(void)
{
    int d1=0, d2=0, ds=0;
    char s1[50], s2[50];
    cin >> s1 >> s2;
    for (int i=0, l=strlen(s1); i < l; i++)
    {
        d1+=abs((int)s1[i]-s1[(i+1)%l]);
        d2+=abs((int)s2[i]-s2[(i+1)%l]);
        ds+=s1[i]-s2[i];
 
 
    }
    if (d1!=d2||ds)
        cout << "s2 ain't shifted s1" << endl;
    else
        cout << "likely s2 is shifted s1" << endl;
    system("pause");
}
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
03.11.2011, 21:29     Является ли первая строка циклическим сдвигом второй строки #4
На сях:
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
int cmp(char *s, char* s2) {
 
    if (strcmp(s,s2)==0) 
        return 1;
 
    if (strlen(s)!=strlen(s2)) 
        return 0;
 
    int len=strlen(s);
 
    for (int c=1; c<len; c++) {
 
        for (int i=0 , i2=c; i<len; i++, i2++ ) {
 
            if (i2==len)
                i2=0;
 
            if (s[i]!=s2[i2])
                break;
 
            if (i==len-1)
                return 1;
 
        }
    }
 
    return 0;
 
}
 
 
int main() {
 
    char s[]="qwerty";
 
    char s2[]="ertyqw";
 
    printf("%d\n",cmp(s,s2));
 
    getch();
    return 0;
}
Yandex
Объявления
03.11.2011, 21:29     Является ли первая строка циклическим сдвигом второй строки
Ответ Создать тему
Опции темы

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