Algorytm knutha-morrisa-pratta do wyszukiwania najdłuższego wzorca
Kod był wyświetlany 962 razy.
    /*
	Name: Program prezentujący zastosowanie algorytmu knutha-morrisa-pratta do wyszukiwania najdłuższego wzorca
	Copyright: GPL GNU
	Date: 01-06-13 19:47
	Description: 
*/

#include <iostream>
#include <string>
#include <cstdlib>

int main()
{
    // Łańcuch do przeszukania
    std::string s;
    // Wzorzec do wyszukania
    std::string pattern;
    std::cout << "Podaj lancuch znakow: ";
    std::getline(std::cin,s);
    std::cout << "Podaj wzorzec: ";
    std::cin >> pattern;
    //Długości maksymalnych prefixów/suffixów
    int PI[pattern.length() + 1];

    PI[0] = -1;
    int suff_length = -1;
    for (int i = 1; i <= pattern.length(); i++)
    {
        while ((suff_length > -1) && (pattern[suff_length] != pattern[i - 1]))
        {
            suff_length = PI[suff_length];
        }
        suff_length++;
        if ((i == pattern.length()) && (pattern[i] != pattern[suff_length]))
        {
            PI[i] = suff_length;
        }
        else
        {
            PI[i] = PI[suff_length];
        }
    }

    //Pozycje wzorca
    int pattern_position = 0;
    suff_length = 0;
    for (int i = 0; i < s.length(); i++)
    {
        while ((suff_length > -1) && (pattern[suff_length] != s[i]))
        {
            suff_length = PI[suff_length];
        }
        if (++suff_length == pattern.length())
        {
            while (pattern_position < i - suff_length + 1)
            {
                pattern_position++;
            }
            std::cout << "Znaleziono wzorzec na pozycji: " << pattern_position
                    << std::endl;
            pattern_position++;
            suff_length = PI[suff_length];
        }
    }
    return 0;
}    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT