Programowanie w C, dwie tablice znaków, szukanie wzorca

Question

Podane mamy  dwie tablice znaków  np.   char napis1[]={"Abab"}   char napis2={"ansusyhabab} program zwraca 1 jeśli ciąg z tablicy napis1 występuję w napis2 a jeśli nie to zwraca 0.

Więc jak byście to zrobili , jaki macie pomysł?

EDIT:
Mamy to zrobić bez używanie funkcji przeznaczonych do tego celu.

Answer 1

Ja bym to zrobił tak:

1. Funkcja nr1 przyjmująca te 2 napisy:

-oblicza długość napisu1 w pętli for,

-w drugiej pętli for, dopóki drugi napis się nie skończy wrzuca do funkcji nr2. oba napisy, numer indeksu funkcji w którym się znajduje i długość pierwszego napisu, jeśli funkcja numer 2 zwróci 1 to funkcja numer 1 też zwraca 1, jak przejdzie cały napis i wyjdzie z pętli to zwraca 0 (bo wcześniej nie zwróciło 1),

2. Funkcja nr2, przyjmuje napisy, indeks napisu2 i długość napisu :

- pętla for działająca dopóki któryś z napisów się nie skończy, porównuje tam napis2 od elementu którego indeks przyjęła funkcja, z napis1, jeśli wyjdzie że któreś znaki nie są równo to zwraca 0, w tej pętli też zliczanie porównanych znaków, jeśli pętla się skończy i z niej wyjdzie (bo wcześniej nie zwróciło 0) to trzeba porównać ilość zliczonych znaków z długością napis1, jeśli różne zwrócić 0, w przeciwnym wypadku zwrócić 1.

Comments

Czy mógłbyś to przedstawić w postaci kodu? wtedy może bym to jakoś przeanalizował i zrozumiał bo jak na razie to tak słabo.

---

Powiedz czego nie rozumiesz?

---

W sumie to takiej zależności między tymi dwoma funkcjami, nie mogę ogarnąć sposoby rozwiązania tego problemu, może dlatego że ja próbowałem to zrobić inaczej no ale mi nie wychodziło.
Więc funkcja1 przyjmuje indeksy tych dwóch napisów ,bo całych tablic nie da się wykorzystać w funkcjach ,tak?
obliczanie długości napisu to nie problem tylko później co się dzieje w tej drugiej pętli for , to jest dla mnie nie zrozumiałe... bo funkcja 1 się jeszcze nie kończy a już wrzuca to do funkcji 2.
Co do funkcji 2 to mam rozumieć że przyjmujemy napis1[0] i porównujemy z każdym kolejnym indeksem napis2 póki napis2==0 , jeśli indeksy się nie zgadzają to zwiększamy indeks napis2 i zaczynamy od nowa? i tak aż któryś napis się nie skończy tak?

---

Funkcja pierwsza

int fun1(char napis1[], char napis2[])

w wywołaniu podajesz samo napis1 i napis2. Po prostu wywołuje tą funkcję.

for(i=0;napis2[i]!='\0';++i){
        if(fun2(napis1,napis2,i,d1)) return 1;
    }

W drugiej funkcji przyjmujesz oba napisy, długość pierwszego napisu i indeks napisu drugiego, który został wrzucony przy wywołaniu w pętli w funkcji pierwszej i porównujesz od napis2[i]!=napis1[j], w pętli zwięszasz i oraz j. i wrzucone z poprzedniej funkcji.

for(j=0;(napis1[j]!='\0')&&(napis2[i]!='\0');++i,++j){
        if(napis2[i]!=napis1[j]) return 0;
        ++x;
    }

 

---

​
#include <stdio.h>
#include <stdlib.h>
int fun1(char napis1[], char napis2[])
{int i,d1;
    for(i=0;napis2[i]!='\0';++i){
        if(fun2(napis1,napis2,i,d1)) return 1;
    }
}
int fun2(char napis1[],char napis2[],int i,int d1)
{   int x=0;
    int j;
    for(j=0;(napis1[j]!='\0');++i,++j)
    {
        if(napis2[i]!=napis1[j]) return 0;
            ++x;
    }
}
int main()
{

    char napis1[]={"xay"};
    char napis2[]={"bauxaxavb"};
    printf("%d",(fun1(napis1,napis2)));
    return 0;
}

Nie jestem w stanie znaleźć błędu, zwraca 0 nawet gdy powinno zwracać 1.

---

Funkcja1:

-gdzie liczenie długości napisu?

-gdzie zwracanie 0?

Funkcja2:

-wywołujesz ją w pierwszej, a ta jest nad nią, więc wyżej powinienieś dać prototyp,

-dlaczego sprawdzasz tylko czy napis1 się kończy? a co z napis2?

-poniżej pętli powinien być warunek, co jak d1!=x a co w przeciwnym wypadku.

#include <stdio.h>

int fun2(char[], char[],int,int);

int fun1(char napis1[], char napis2[]){
    int i,d1;
    for(d1=0;napis1[d1]!='\0';++d1);
    for(i=0;napis2[i]!='\0';++i){
        if(fun2(napis1,napis2,i,d1)) return 1;
    }
    return 0;
}

int fun2(char napis1[], char napis2[], int i,int d1){
    int j,x=0;
    for(j=0;(napis1[j]!='\0')&&(napis2[i]!='\0');++i,++j){
        if(napis2[i]!=napis1[j]) return 0;
        ++x;
    }
    if(d1!=x) return 0;
    return 1;
}

int main(){


    char napis1[]={"xay"};
    char napis2[]={"bauxaxavb"};
    printf("%d\n",fun1(napis1,napis2));

    return 0;
}

Ja to zrobiłem tak. Sprawdzałem dla różnych sytuacji i działa jak trzeba, o ile dobrze zrozumiałem polecenie i czegoś nie pomyliłem. Nie podałem Ci od razu kodu, żebyś trochę to przemyślał. Mam nadzieję, że zrozumiałeś i wiesz już jak to zrobić.

Answer 2

Pierwszy algorytm który wpadł mi do głowy o złożoności O ( n * m ) gdzie n i m to długość napisów <- czyli kiepsa złożoność. Jak będziesz chciał lepszą złożoność algorytmu to pisz :P

#include <iostream>
#include <string>
using namespace std;
int main(){
    // zakldamy ze napis 2 jest zawsze dluzszy od 1
   string napis1,napis2; // nasze napisy i sprawdzamy napis 1  w napisie 2 !!
   cin>>napis1>>napis2;
   int d1 = napis1.length();
   int d2 = napis2.length();
   bool czy_znajduje = true;
   for ( int i = 0 ; i < d2 - d1; i++ ){
        czy_znajduje = true;
        for ( int j = 0; j < d1; j++ ){

            if ( napis2[i+j] != napis1[j] ) czy_znajduje = false;
        }
       if ( czy_znajduje ){cout<<"jest wzorzec"; return 0; }
   }
    cout<<"niema wzorca";
}