?? morrispratt.cpp
字號:
// MorrisPratt.cpp: implementation of the MorrisPratt class.
//
//////////////////////////////////////////////////////////////////////
#include "MorrisPratt.h"
#include <stdio.h>
#include <string.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
MorrisPratt::MorrisPratt() : m_pNum(0), m_mpNext(NULL)
{}
MorrisPratt::~MorrisPratt()
{
delete [] m_mpNext;
m_mpNext = NULL;
}
void MorrisPratt::test()
{
TimeIt tt;
MorrisPratt mp;
mp.search();
mp.OUTPUT(tt.GetMSecElapsed());
}
void MorrisPratt::preMp(char *x, int m, int mpNext[])
{
int i, j;
i = 0;
j = mpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = mpNext[j];
mpNext[++i] = ++j;
}
}
void MorrisPratt::search()
{
char *x = (char*)m_search,
*y = (char*)m_context;
int m = strlen(m_search),
n = strlen(m_context);
int i, j;
if (m_pNum < m) {
delete [] m_mpNext;
m_mpNext = new int[m+1];
m_pNum = m;
}
/* Preprocessing */
preMp(x, m, m_mpNext);
/* Searching */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = m_mpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = m_mpNext[i];
}
}
delete [] m_mpNext;
m_mpNext = NULL;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -