Zastosowanie uproszczonego algorytmu Boyer'a-Moore'a do wyszukiwania wzorca w tekście
Kod był wyświetlany 891 razy.
    	/*
	Name:Program prezentujący zastosowanie uproszczonego algorytmu Boyer'a-Moore'a do wyszukiwania wzorca w tekście
	Copyright: GPL GNU
	Date: 30-05-13 16:09
	Description: 
*/

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

const int ALPH_START_CHAR = 65; // PIERWSZY ZNAK
const int ALPH_STOP_CHAR = 122; // OSTATNI ZNAK

int main()
{
    // Łańcuch do przeszukania
    std::string s;
    // Wzorzec do wyszukania
    std::string pattern;
    std::cout << "Podaj lancuch znakow: ";
    std::cin >> s;
    std::cout << "Podaj wzorzec: ";
    std::cin >> pattern;

    int occur_last[ALPH_STOP_CHAR - ALPH_START_CHAR + 1];

    for (int i = 0; i <= ALPH_STOP_CHAR - ALPH_START_CHAR; i++)
    {
        occur_last[i] = -1;
    }
    for (int i = 0; i < pattern.length(); i++)
    {
        occur_last[pattern[i] - ALPH_START_CHAR] = i;
    }

    int pattern_position = 0;
    int i = 0;
    while (i <= s.length() - pattern.length())
    {
        int j = pattern.length() - 1;
        while ((j > -1) && (pattern[j] == s[i + j]))
        {
            j--;
        }
        if (j == -1)
        {
            while (pattern_position < i)
            {
                pattern_position++;
            }
            pattern_position++;
            std::cout << "ZNALEZIONO WZORZEC NA POZYCJI: " << pattern_position << std::endl;
            i++;
        }
        else
        {
            i += std::max(1, j - occur_last[s[i + j] - ALPH_START_CHAR]);
        }
    }

    return 0;
}    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT