高考历史、文综历史专题复习【全部完成】

用语言实现蛮力法、Horspool、Boyer-Moore、Knuth-Morris-Pratt算法，针对不同的数据规模研究它们的性能。数据规模应在100，000以上。


int BruteForceStringMatch(string str, string pattern)
{
for( int i = 0; i <= str.size()- pattern.size(); i++ )
{
int j = 0;
while( (j < pattern.size()) && (pattern[j] == str[i+j]))
{
j++;

}
if( j == pattern.size())
return i;
}
return (-1);
}
void ShiftTable(string pattern, int table[], int l)
{
for(int i = 0; i < 127; i++)
table[i] = l;
for(int j = 0; j < l-1; j++)
table[pattern[j]] = l-1-j;
}
void HorspoolMatch(string str, int table[], string pSize)

int main()
{
string a = "abcdefg";
string mode = "z";
cout<<BruteForceStringMatch(a, mode)<<endl;
return 0;
}



#include<iostream>
using namespace std;

const int HASH_SIZE=256;
int table[HASH_SIZE];//对应字符表的255个字符建哈希表,表示对不匹配字符 向右移动的距离

void ShiftTable(char pattern[]){
/*建立一个以字母表中字符为索引的Table数组*/
int m=strlen(pattern);
for(int i=0;i<HASH_SIZE;i++)
table[i]=m;
for(int j=0;j<m-1;j++)
table[ pattern[j] ]=m-1-j;

}

int HorspoolMatching(char pattern[],char text[]){//平均效率为O(n)
/*
pre:模式pattern，文本text
post:第一个匹配字串的最左端字符下标，没有找到匹配字串返回-1
*/
ShiftTable(pattern);
int m=strlen(pattern);
int n=strlen(text);

int i=m-1;
while(i <= n-1){
int k=0; //匹配的字符个数
while(k<=m-1 && pattern[m-1-k] == text[i-k] )
k++;
if(k==m)
return i-m+1;
else
i=i+table[ text[i] ]; //以模式最后一个字符确定移动距离,与B.M算法的最大区别，简化形式
}

return -1;
}


int main(){

char p[20],t[1000];

while(cin>>t && t!="."){

int times=5;
while(times--){
cin>>p;
cout<<HorspoolMatching(p,t)<<endl;
}

}
return 1;
}


#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#ifndef ssize_t
typedef off_t ssize_t;
#endif
using namespace std;
void compute_last_occurrence(const string& needle , vector<ssize_t>& last_occurrence)
{
last_occurrence.resize(256,-1);
for ( size_t i = 0 ; i < needle.size() ; i++ )
{
last_occurrence[needle[i]] = i;
}
}
void compute_prefix_function(const string& needle , vector<size_t>& prefix_function)
{
if ( needle.size() == 0 )
{
return;
}
prefix_function.resize( needle.size() , 0 );
size_t d = 0 ;
for ( size_t i = 1 ; i < needle.size() ; i++ )
{