algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm KMP (Knutha-Morrisa-Pratta) - Implementacja w C/C++
Ocena użytkownikóww: *****  / 6
SłabyŚwietny
Nadesłany przez Bartosz Bednarczyk, 20 sierpnia 2012 19:29
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

kmp.cpp:
//Algorytm Knutha-Morrisa-Pratta - wyszukiwanie wzorca
//Bartosz Bednarczyk
//www.algorytm.org

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

void Pref( vector<int> &P, string &S )
{
	unsigned int t = 0, i, n = S.size();
	P.resize(n+1, 0);

	for( i = 2; i < n; i++ )
	{
		while (t > 0 && S[t + 1] != S[i]) t = P[t];
		if( S[t+1] == S[i] ) t++;
		P[i] = t;
	}
}

void KMP( string &T, string &W )
{
	string S = "#" + W + "#" + T;
	vector<int> P;
	Pref(P, S);

	unsigned int i, ws = W.size();

	for( i = ws + 2; i < S.size(); i++ )
	{
		//wypisz pozycje wzorca w tekscie
		if( P[i] == ws ) printf("%d\n", i-ws-ws);
	}
}

int main()
{
	//podaj tekst oraz wzorzec oddzielone spacja
	string T, W;
	cin >> T >> W;
	KMP(T, W);

	return 0;
}
Dodaj komentarz