Версия для печати темы

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

Форум «Всё о Паскале» _ Ада и другие языки _ Прямой алгоритм поиск. СИ

Автор: Eichhorn 3.06.2011 12:36

При запуске программы пользователь вводит две строки, длины которых ограничены 1024. Вывести индексы всех вхождений второй строки в первую, используя Прямой алгоритм.
Не могу понять как это впринципе осуществляется. Сам порядок решения. Подскажите, пожалуйста.

Автор: Lapp 3.06.2011 13:54

Цитата(Eichhorn @ 3.06.2011 9:36) *
Вывести индексы всех вхождений второй строки в первую, используя Прямой алгоритм.
Не могу понять как это впринципе осуществляется. Сам порядок решения.

Ну, как-то вот так.. Я, правда, не знаю, что такое "прямой алгоритм". Думаю, что это он и есть )). Если ошибаюсь - поправьте, плз.
l= strlen(c2);
i= 0;
while (c1[i]>0) {
  j= 0;
  while ((c2[j]>0) && (c2[j]==c1[i+j])) j++;
  if (j=l) printf("%d\n",i++);
}


исправлено )

Автор: IUnknown 3.06.2011 14:37

Я бы, наверное, сделал вот так:

    char *pc1 = c1;
    while(*pc1++)
    {
        char *p = pc1;
        char *pc2 = c2;
        while((*p != 0) && (*pc2 != 0) && (*p++ == *pc2++));
        
        if(!(*pc2)) printf("%d\n", (pc1 - c1));
    }


blink.gif then? Пошел перечитывать азбуку... Я явно что-то упускаю...

Автор: Lapp 3.06.2011 14:48

Цитата(IUnknown @ 3.06.2011 11:37) *
blink.gif then? Пошел перечитывать азбуку... Я явно что-то упускаю...

Спасибо, исправляю.. ))

Автор: Eichhorn 3.06.2011 15:06


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

int main(){
   char c1[]="mamapopmamakjhmama";
   char c2[]="mama";
   char *pc1=c1;
   
while(*pc1++)
	{
		char *p = pc1;
		char *pc2 = c2;
		while((*p != 0) && (*pc2 != 0) && (*p++ == *pc2++));
		
		if(!(*pc2)) printf("%d\n", (pc1 - c1));
	}
	getch();
	return 0;
}


Вот такой код получается. Но не считается певрое вхождение, когда индекс равен нулю.. И можно пояснить, что значит рс1 и рс2?

Автор: IUnknown 3.06.2011 15:45

Говорила мне мама - не пиши на С, проблемы на пустом месте возникают. pc1 надо увеличивать в другом месте:

while(*pc1)
    {
        char *p = pc1;
        char *pc2 = c2;
        while((*p != 0) && (*pc2 != 0) && (*p++ == *pc2++));
        
        if(!(*pc2)) printf("%d\n", (pc1 - c1));

        pc1++;  /* <---  Вот тут */
    }
, тогда должно сработать. Проверь, у меня сейчас компилятора С-шного под рукой нет...

Цитата
И можно пояснить, что значит рс1 и рс2?
Можно, это временные указатели на строку. Чтобы сравнивать подстроки между собой - можно воспользоваться тем способом, как это делается в Паскале (что продемонстрировал Lapp) - т.е., обращаться к символу по индексу, а можно сделать в духе С, используя указатель на строку... То есть:
Цитата
        char *p = pc1;  // начинаем просмотр с текущего места основной строки
        char *pc2 = c2; // и с начала подстроки

        // пока не дошли до конца строки и не дошли до конца подстроки,
        // и очередные символы равны между собой - продвигаемся в обеих
        // строках дальше
        while((*p != 0) && (*pc2 != 0) && (*p++ == *pc2++));
, а потом достаточно сравнить *pc2 с нулем, чтобы понять, нашли мы полное вхождение подстроки в строку, или частичное. Если там 0 - значит, полное, пробежали до конца подстроки, можно выводить номер позиции...

Автор: Eichhorn 3.06.2011 16:14

Огромное спасибо!!! Всё поняла, во всём разобралась.

Автор: Lapp 4.06.2011 8:25

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

  int l= strlen(c2);
  int i= 0;
  while (c1[i]>0) {
    int j= 0;
    while ((c2[j]>0) && (c1[i]>0) && (c2[j]==c1[i+j])) j++;
    if (j==l) printf("%d\n",i);
    i++;
  }

Согласен, что длину я зря приплел.. (