Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Вариации подстроки в строке.

Автор: .talisman 22.5.2005, 11:04

Задача:
Подсчитать колличество слов длины К из данных N букв, не содержащих данное подслово.

есть символьные массивы:
А и Б.
Оба вводятся с клавиатуры в ходе выполнения программы. Строка Б является подстрокой А. Еще есть переменная len, которая определяет длину искомого слова. Например:

пользователь вводит строку: "abcd".
подстроку: "bc".
длину слова: "3".

формируем слова:
abc -- bc имеет место приутствовать, каунт не увеличиваем.
abd -- bc нет, увеличиваем каунт на единицу.
bcd -- bc есть, каунт не увеличиваем.

Общий алгоритм:
1. Получаем данные.
2. Формируем новые строки.
3. Проверяем содержание подстроки в новых строках и если она есть, то увеличиваем каунт.
4. записываем в файл.

Вопрос:
как перебрать всевозможные коомбинации при формировании новой строки? (порядок букв менять нельзя, то есть в предыдущем примере подстроки типа dcb нет).

заранее спасибо.

Автор: maxim1000 22.5.2005, 13:28

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

Код


int f(string s,int i,int k,string Alphabet,string Target)
{
  if(s.length()==k)//одно из слов длины K
  {
    if(s.Contains(Target))//если содержит слово - не подходит
      return 0;
    else//а если нет - то, что надо
      return 1;
  }
  if(i==Alphabet.length())//нечего больше добавлять (исходное слово закончилось)
    return 0;
  int count=0;
  count+=f(s,i+1,k,Alphabet,Target);//соотв.случаю, когда мы не добавляем текущую букву
  count+=f(s+Alphabet[i],i+1,k,Alphabet,Target);//когда добавляем
  return count;
}
...
  //где-то в далекой функции main()
  result=f("",0,k,"qwert","wt");

если сделать класс string с нужными методами, то эта программка может даже скомпилироваться smile

Автор: Akina 23.5.2005, 07:55

Опять элементарная задачка... ДУМАЙ!!! а не программы пиши... формула получается ВПРЯМУЮ...

Автор: segmentation_fault 23.5.2005, 18:25

Ну формула-то впрямую получается, но это уже больше математика чем информатика. Может их препод хочет именно чтобы они алгоритм написали, а не нашли формулу и вставляли туда нужные значения.

Автор: .talisman 24.5.2005, 06:16

формула надо, так как комбинаторику проходим. учится осталось три дня, а лаба еще не сдана.
дай плиз формулу =)
обещаю все потом выучить =)

Автор: .talisman 24.5.2005, 11:49

насчет всех подслов фуормулу нашел:
(m!)/(n!-(m!-n!), где m длина строки, а n длина генерируемых слов.

в предыдущем примере m=4, а n=3. Получаем:
(4!)/(3!-(4!-3!) = 4!/3! = 4.

а вот как вычесть строки содержащие введенную подстроку я не знаю =(

Автор: Akina 24.5.2005, 11:53

А какая разница - слова в строке или подстрока в слове?

Автор: .talisman 24.5.2005, 11:59

что-то я не понял вашего вопроса.
разницы никакой, но какое отношение этот пример имеет к данному случаю?

хотя нет, разница в том, что слова в строке разделены пробелами.

Автор: Akina 24.5.2005, 12:08

Цитата

насчет всех подслов фуормулу нашел:

Только неправильную. С арифметикой сложности... приведи подобные, получится 1, независимо от m и n... уж как ты там подстановку сделал и посчитал не то что на самом деле получается...

Цитата

слова в строке разделены пробелами

Слово - совокупность символов. Пробел - такой же символ, как буква, цифра или там запятая, пока не определен его специальный статус. В твоем задании он НЕ определен. Мысли абстрактнее...

Автор: .talisman 24.5.2005, 12:33

так ничего и не понял smile

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

Автор: .talisman 24.5.2005, 14:05

по совету maxim1000 попробовал воспользоваться рекурсией.
писалось в борлан си++ 3.1, 1992 года, досовская =)

проблема -- результат всегда равен нулю.

Код

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>
#include <string.h>

int f(char *s,int i,int len,char *a1,char *a2)
{
    if(strlen(s)==len)
    {
        if(strstr(s, a2))
            return 0;
        else
            return 1;
    }
    if(i==strlen(a1))
        return 0;
    int count=0;
    char tmp[5];
    tmp[0]=a1[i];
    tmp[1]=NULL;
    count+=f(s, i+1, len, a1, a2);
    count+=f(tmp, i+1, len, a1, a2);
    return count;
}

void main()
{
    char a1[20], a2[20];
    int len, result;
    clrscr();
    printf("enter string: ");
    scanf("%s", a1);
    printf("enter substring: ");
    scanf("%s", a2);
    printf("enter lenght of generic word: ");
    scanf("%i", len);
    result=f("", 0, len, a1, a2);
    printf("%i", result);
    getch();
}

Автор: maxim1000 25.5.2005, 03:15

по-моему, здесь получилось не совсем то, что я предполагал:

Цитата

count+=f(s+Alphabet[i],i+1,k,Alphabet,Target);//когда добавляем

Цитата

count+=f(tmp, i+1, len, a1, a2);

в алгоритме в функцию передается строка с добавлением одного символа
а в реализации передается строка из одного символа
тут надо было бы выделить память (new или массивом) под новую строку, записать туда старую и добавить еще один символ
можно вообще использовать один буфер для всех вызовов: просто сделать его достаточно большим (k+1 должно хватить), и перед вторым рекурсивным вызовом добавлять туда символ, а после - удалять (т.к. этот буфер используется и предыдущими вызовами)

Код


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>
#include <string.h>

int f(char *s,int i,int len,char *a1,char *a2)
{
    if(strlen(s)==len)
    {
        if(strstr(s, a2))
            return 0;
        else
            return 1;
    }
    if(i==strlen(a1))
        return 0;
    int count=0;
    count+=f(s, i+1, len, a1, a2);
    {//add an a1[i] to s
      char *p=s;
      while(*p)
        p++;
      *p++=a1[i];
      *p=0;
    }
    count+=f(s, i+1, len, a1, a2);
    {//clean up:remove last character from s
      char *p=s;
      while(*p)
        p++;
      p--;
      *p=0;
    }
    return count;
}

void main()
{
    char a1[20], a2[20];
    char s[100];
    int len, result;
    printf("enter string: ");
    scanf("%s", a1);
    printf("enter substring: ");
    scanf("%s", a2);
    printf("enter lenght of generic word: ");
    scanf("%d", &len);
    s[0]=0;
    result=f(s, 0, len, a1, a2);
    printf("%i", result);
    getch();
}

P.S.
кстати, когда с помощью scanf читается число, надо давать адрес переменной для созранения результата - перед len надо ставить &...

Автор: .talisman 25.5.2005, 14:49

огромное спасибо.
насчет амперсанда знал, опечатался =)