Объясните, пожалуйсто этот алгоритм. Те описания, что я находил мне совсем не понятны, да и в разных источниках они очень различаются.
Привет
INR>Объясните, пожалуйсто этот алгоритм. Те описания, что я находил мне совсем не понятны, да и в разных источниках они очень различаются.
Чем могу помочь.
1. Ссылками. Читать Кормена, там есть соответствующая глава.
2. Идея. Идея похожа на Automation-matcher, только вместо вычисления суффикс-функции, вычисляется префикс-функция, таблица которой меньше на размер алфавита, вычислять которую можно за O(длина образца), и по которой можно организовать Automation-алгоритм за O(длина текста) в амортизационном смысле.
3. Мой исходник.
class CPatternMatcher
{
protected:
char* m_Pattern;
int m_PatternLen;
public:
CPatternMatcher(const char* pattern)
{
assert(pattern);
m_PatternLen = strlen(pattern);
assert( m_PatternLen );
m_Pattern = new char[m_PatternLen + 1];
memcpy(m_Pattern, pattern, m_PatternLen + 1);
}
virtual TIntVector getMatchings(const char* sample) = 0;
virtual ~CPatternMatcher()
{
delete[] m_Pattern;
}
};
class CKnuthMorrisPrattMatcher : public CPatternMatcher
{
private:
int* m_PrefixFunction;
public:
CKnuthMorrisPrattMatcher(const char* pattern) : CPatternMatcher(pattern)
{
m_PrefixFunction = new int[m_PatternLen];
m_PrefixFunction[0] = -1;
for (int i = 1; i < m_PatternLen; ++i)
{
int q = m_PrefixFunction[i - 1];
while ( (q >= 0) && (m_Pattern[q + 1] != m_Pattern[i]) )
q = m_PrefixFunction[q];
if (m_Pattern[q + 1] == m_Pattern[i])
++q;
m_PrefixFunction[i] = q;
}
}
virtual ~CKnuthMorrisPrattMatcher()
{
delete[] m_PrefixFunction;
}
virtual TIntVector getMatchings(const char* sample)
{
TIntVector Result;
int sampleLen = strlen(sample);
int q = -1;
for (int i = 0; i < sampleLen; ++i)
{
while ( (q >= 0) && (m_Pattern[q + 1] != sample[i]) )
q = m_PrefixFunction[q];
if (m_Pattern[q + 1] == sample[i])
++q;
if (q == m_PatternLen - 1)
{
Result.push_back(i - m_PatternLen + 1);
q = m_PrefixFunction[m_PatternLen - 1];
}
}
return Result;
}
};
... << RSDN@Home 1.1.4 beta 3 rev. 207>>
Fundamental Algorithms for a Declarative Pattern Matching System (Stefan Kurtz)
http://home.od.ua/~relayer/algo/text/stefankurtz.zip
Здравствуйте, Den Raskovalov, Вы писали:
DR>Привет
INR>>Объясните, пожалуйсто этот алгоритм. Те описания, что я находил мне совсем не понятны, да и в разных источниках они очень различаются.
DR>Чем могу помочь.
DR>1. Ссылками. Читать Кормена, там есть соответствующая глава.
DR>2. Идея. Идея похожа на Automation-matcher, только вместо вычисления суффикс-функции, вычисляется префикс-функция, таблица которой меньше на размер алфавита, вычислять которую можно за O(длина образца), и по которой можно организовать Automation-алгоритм за O(длина текста) в амортизационном смысле.
DR>3. Мой исходник.
DR>DR>class CPatternMatcher
DR>{
DR>protected:
DR> char* m_Pattern;
DR> int m_PatternLen;
DR>public:
DR> CPatternMatcher(const char* pattern)
DR> {
DR> assert(pattern);
DR> m_PatternLen = strlen(pattern);
DR> assert( m_PatternLen );
DR> m_Pattern = new char[m_PatternLen + 1];
DR> memcpy(m_Pattern, pattern, m_PatternLen + 1);
DR> }
DR> virtual TIntVector getMatchings(const char* sample) = 0;
DR> virtual ~CPatternMatcher()
DR> {
DR> delete[] m_Pattern;
DR> }
DR>};
DR>class CKnuthMorrisPrattMatcher : public CPatternMatcher
DR>{
DR>private:
DR> int* m_PrefixFunction;
DR>public:
DR> CKnuthMorrisPrattMatcher(const char* pattern) : CPatternMatcher(pattern)
DR> {
DR> m_PrefixFunction = new int[m_PatternLen];
DR> m_PrefixFunction[0] = -1;
DR> for (int i = 1; i < m_PatternLen; ++i)
DR> {
DR> int q = m_PrefixFunction[i - 1];
DR> while ( (q >= 0) && (m_Pattern[q + 1] != m_Pattern[i]) )
DR> q = m_PrefixFunction[q];
DR> if (m_Pattern[q + 1] == m_Pattern[i])
DR> ++q;
DR> m_PrefixFunction[i] = q;
DR> }
DR> }
DR> virtual ~CKnuthMorrisPrattMatcher()
DR> {
DR> delete[] m_PrefixFunction;
DR> }
DR> virtual TIntVector getMatchings(const char* sample)
DR> {
DR> TIntVector Result;
DR> int sampleLen = strlen(sample);
DR> int q = -1;
DR> for (int i = 0; i < sampleLen; ++i)
DR> {
DR> while ( (q >= 0) && (m_Pattern[q + 1] != sample[i]) )
DR> q = m_PrefixFunction[q];
DR> if (m_Pattern[q + 1] == sample[i])
DR> ++q;
DR> if (q == m_PatternLen - 1)
DR> {
DR> Result.push_back(i - m_PatternLen + 1);
DR> q = m_PrefixFunction[m_PatternLen - 1];
DR> }
DR> }
DR> return Result;
DR> }
DR>};
DR>
Не можете ли вы мне помочь обработать этот алгоритм так, чтобы он для всех i искал максимальный префикс слова x[1]x[2]...x[i] являющийся инвертным суффиксом этого слова, то есть надо суффикс прочитать в другую сторону. Можно дать псевдокод, исходник, словесное описание.
