C++ zliczanie wystąpień podciągu w ciągu

Question

Cześć, piszę program mający zliczać liczbę wystąpień podanego podciągu w ciągu. Niestety nie mogę operować na stringach (chyba) ani korzystać ze specjalnych funkcji, ponieważ jest to przedmiot "programowanie niskopoziomowe"... Czy ktoś widzi błąd w kodzie? Dlaczego on nie działa poprawnie? Proszę o pomoc.

#include <stdio.h>
#define N 1000

int dlugosc_ciagu(char tab[], int ile_elementow)
{
	int licznik=0;
	for(int i=0; i<ile_elementow; i++)
	{
		if(tab[i]!='\0')licznik++;
	}
	return licznik;
}

int main()
{
	char ciag[N], podciag[N], warunek=0, l_wystapien=0;
	printf("Podaj ciag: ");
	scanf("%s",&ciag);
	printf("Podaj podciag: ");
	scanf("%s",&podciag);
	
	for(int i=0; i<N; i+=dlugosc_ciagu(podciag,N))
	{
		for(int j=0; j<dlugosc_ciagu(podciag,N); j++)
		{
			if(ciag[i+j]==podciag[j])warunek=1;
			else warunek=0;
		}
		if(warunek==1)l_wystapien++;
		warunek=0;
	}
	printf("Liczba wystapien podanego podciagu w calym ciagu: %d",l_wystapien);
	return 0;
}

 

Answer 1

1. Po wczytaniu napisów oblicz ich długości i zapisz w zmiennych dlugosc1, dlugosc2.
2. Jeżeli długość podciągu jest większa od długości ciągu zakończ algorytm.
3. Zewnętrzną pętle iterujesz od 0 do (dlugosc1-dlugosc2-1), iterator i zwiększasz o 1 (Twój algorytm wychodzi poza długość ciągu)
4. Przed rozpoczęciem pętli wewnętrznej ustawiasz warunek na 1.
5. W pętli wewnętrznej sprawdzasz czy porównywane znaki są różne. Jeżeli tak to zmieniasz warunek na 0 i kończysz pętlę.

Comments

Dzięki. Mam jednak pytanie co do pkt. 3. - dlaczego iteracja akurat do dlugosc1-dlugosc2-1 zamiast po prostu dlugosc1-1? Wydaje mi się jakbyśmy pomijali wtedy koncówkę ciągu

---

Aby napisy były równe muszą mieć równą długość. Jeżeli ten warunek nie jest spełniony to nie ma sensu dalej sprawdzać.

Answer 2

https://pl.wikipedia.org/wiki/Algorytm_Knutha-Morrisa-Pratta To co masz jest bardzo niewydajnie.

Akurat na platformach wbudowanych nagłówek <string.h> jest obecny. Ja bym zastosował z zastrzeżeniem że wyraźnie tego nie zabroniono.