Самая длинная подстрока - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Самая длинная подстрока (http://forum.oszone.net/showthread.php?t=268695)

Самая длинная подстрока

Помогите решить задачу.
Дана строка, состоящая из маленьких латинских букв. Ваша задача — найти длину ее самой длинной подстроки, встречающейся в строке хотя бы 2 раза. Вхождения подстрок могут перекрываться.
Максимальная длина строки - 100 символов.

В гугле море алгоритмов для нахождения подстроки, выбирайте любой. Думаю проверить кол-во вхождений и найти самую длинную не составит труда.

Цитата:

Цитата ViRTaCe

В гугле море алгоритмов для нахождения подстроки, выбирайте любой. Думаю проверить кол-во вхождений и найти самую длинную не составит труда. »

Программа выглядит вот-так.

Код:

#include <stdio.h>

#include <string.h>

#include <conio.h>

int HowMany(char string[], char word[]) {

    char *p = strstr(string, word);

    if(!p)

    return 0;

    return 1 + HowMany(p + strlen(word), word);

}

int HowMany(char *, char *);

int main()

{

    char string[200];

    gets(string);

    int maxLen = 0;

    int mn = 0;

    while(maxLen != 0 && mn < 2) {

                 char * pch = strtok (string," ");  // получаем первое слово

    char * word = 0; // самое длинное слово

 

    int length = strlen(pch);          // определяем длинну первого слова

 

    int maxLen = 0; // самое длинное слово

 

      while (pch != NULL)                         // пока есть слова

      {

          length = strlen(pch);        // определяем длинну слова

 

          if (maxLen < length )        // определяем самое длинное слово

          {

              maxLen = length;

              word = pch;              // сохраняем указатель на текущее слово

          }

 

          pch = strtok (NULL, " "); // получаем следующее слово

          }

          mn = HowMany(string, word);

          }

          printf("%d\n", mn);

 

      /*cout << "Самое длинное слово: " << word

           << " , его длина равна: " << maxLen

           << " символам " << endl;*/

           getch();

 return 0;

}

Как выбрать подстроку?

Цитата:

Цитата MahovIV

Программа выглядит вот-так. »

Здесь ищутся слова, а не подстроки.

Цитата:

Цитата Iska

Цитата MahovIV:
Программа выглядит вот-так. »
Здесь ищутся слова, а не подстроки. »

Я пробовал сделать вот-так.

Код:

#include <stdio.h>

#include <string.h>

#include <conio.h>

int HowMany(char string[], char word[]) {

    char *p = strstr(string, word);

    if(!p)

    return 0;

    return 1 + HowMany(p + strlen(word), word);

}

int HowMany(char *, char *);

int main() {

    

    int i, j = 0, k = 0, pr = 0, mn = 0;

    char s[100], c[100];

    gets(s);

    while(j < strlen(s)) {

            while(k < strlen(s)) {

                    for(i = 0; i < strlen(s); i++) {

                          c[i] = s[i + k];

                          }

                          mn = strlen(c);

                          pr = HowMany(s, c);

                          if(pr >= 2) {

                                break;

                                }

                                delete(c);

                                k++;

                                }

                                delete(c);

                                k = 0;

                                j++;

                                }

                                if(pr >= 2) {

                                printf("%d\n", mn);

                                }

                                else {

                                     printf("0\n");

                                     }

                                getch();

                                return 0;

                                }

Но не во всех случаях программа выдаёт правильные результаты.
Что я делаю не так?

Цитата:

Цитата ViRTaCe

Вы посмотрите сами.
https://www.google.com.ua/search?ie=UTF-8&hl=ru&q=%D0%A1%D0%B0%D0%BC%D0%B0%D1%8F%20%D0%B4%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F%20%D0%BF%D0%BE %D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0%20%D0%A1%D0%B8#hl=ru&q=%D0%A1%D0%B0%D0%BC%D0%B0%D1%8F+%D0 %B4%D0%BB%D0%B8%D0%BD%D0%BD%D0%B0%D1%8F+%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0+%D0%A 1%D0%B8
Поисковая система - это не решение всех проблем.

Не так.

1. Получить перечень всех уникальных подстрок, входящих в исходную. Минимальная — один символ, максимальная — вся исходная строка.

2. Принять максимальную длину искомой подстроки за «0».

3. Перебирая все полученные в п.1 уникальные подстроки, проверять количество вхождений каждой из них в исходную строку.
3а) если количество вхождений окажется больше единицы (т.е., подстрока встречается в искомой хотя бы дважды) и её длина больше, нежели текущее значение максимальной длины из п.2 — принять её максимальную длину за искомую.

Решив эти частичные задачи — составные части алгоритма — Вы получите правильный результат. Не забудьте, что, согласно условия:

Цитата:

Цитата MahovIV

Вхождения подстрок могут перекрываться. »

строка «abbbbc», например, будет содержать три вхождения подстроки «bb».

Цитата:

Цитата Iska

Не так.
1. Получить перечень всех уникальных подстрок, входящих в исходную. Минимальная — один символ, максимальная — вся исходная строка.
2. Принять максимальную длину искомой подстроки за «0».
3. Перебирая все полученные в п.1 уникальные подстроки, проверять количество вхождений каждой из них в исходную строку.
3а) если количество вхождений окажется больше единицы (т.е., подстрока встречается в искомой хотя бы дважды) и её длина больше, нежели текущее значение максимальной длины из п.2 — принять её максимальную длину за искомую.
Решив эти частичные задачи — составные части алгоритма — Вы получите правильный результат. Не забудьте, что, согласно условия:
Цитата MahovIV:
Вхождения подстрок могут перекрываться. »
строка «abbbbc», например, будет содержать три вхождения подстроки «bb». »

Подскажите, что мне нужно исправить в коде?

Код:

#include <stdio.h>

#include <string.h>

#include <conio.h>

int HowMany(char string[], char word[]) {

    char *p = strstr(string, word);

    if(!p)

    return 0;

    return 1 + HowMany(p + strlen(word), word);

}

int HowMany(char *, char *);

int main() {

    

    int i, j = 0, k = 0, pr = 0, mn = 0, l = 0, f = 0;

    char s[100], c[100];

    gets(s);

    while(j < strlen(s)) {

                    for(i = 0; i < strlen(s) - j; i++) {

                          c[i] = s[i + k];

                          }

                          k++;

                          mn = strlen(c);

                          pr = HowMany(s, c);

                          if(pr >= 2) {

                                break;

                                }

                                l++;

                                j++;

                                }

                                if(pr >= 2) {

                                printf("%d\n", mn);

                                }

                                else {

                                     printf("0\n");

                                     }

                                getch();

                                return 0;

                                }

MahovIV,

Цитата:

Цитата MahovIV

Подскажите, что мне нужно исправить в коде? »

вам надо спокойно сесть, выключить компьютер (уйти в другую комнату), нарисовать алгоритм на бумаге (схемой, картинкой, не важно), понять его, понять "что и как хочется сделать", и потом спокойно написать программу "своей" головой.
От того, что вы копируете чужой код и просите его для вас переписать толку не будет.
Код следует переписать полностью.
И для строк используйте string, а не char *.
Чтобы с полной уверенностью сказать "Это я сам!"