?? kmp.cpp
字號:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
/***************************聲明函數(shù)*************************************/
int CharKmp(string,string,int); //KMP算法
void GetNext(); //求Next值
void Install(string,string); //初始化操作
void QuickSort(string str[],int low,int high);//將篩選出來的字串進行排序
int Partition(string str[],int low,int high);//運用快速排序法將整個字串分成兩部分
int GetLength();
/***************************定義變量*************************************/
string s1,t1;
int m,n;
char*s;
char*t;
int*next;
static string model;
int amount=0;
int length;
/************************************************************************/
int main()
{
//定義變量
string *raw;
string *sort;
string b;
raw = new string[(length=GetLength())];
sort = new string[length];
int i;
//從文件中讀取數(shù)據(jù)
ifstream fin;
fin.open("G:\\KMP\\yuanshi.txt");
if(!fin){
cout<<"不能打開文件!"<<endl;
return 0;
}
for(i=0;i<length;i++)
{
fin>>b;
raw[i]=b;
}
fin.close();
//自定義輸入匹配模板
cout<<"請輸入匹配的模板: ";
cin>>model;
//在全部數(shù)據(jù)中查找與模板相符合的數(shù)據(jù)然后輸出
for(i=0;i<length;i++)
{
int position=0;
position=CharKmp(raw[i],model,1);
if(position!=0)
{
sort[amount]=raw[i];
amount++;
}
}
if(amount==0)
cout<<"原始數(shù)據(jù)中沒有與輸入模板相匹配的值!"<<endl;
else
{
QuickSort(sort,0,amount-1);
cout<<"匹配并排序之后的結(jié)果為:"<<endl;
for(i=0;i<amount;i++)
cout<<sort[i]<<" "<<endl;
}
delete[] s;
delete[] t;
delete[] next;
return 0;
}
/************************************************************************/
//KMP算法函數(shù)
int CharKmp(string s0,string t0,int pos)
{
Install(s0,t0);
GetNext();
int i=pos;
int j=1;
while (i<=((int)(s[0]))&&j<=((int)t[0]))
{
if(j==0||(s[i]==t[j]))
{
++i;
++j;
}
else
j=next[j];
}
if(j==((int)t[0])+1)
return 1;
else
return 0;
}
/************************************************************************/
//相當于初始化操作,求字串長度及每個字符
void Install(string ss,string tt)
{
s1=ss;
t1=tt;
m=s1.length();
n=t1.length();
s=new char[m+1];
t=new char[n+1];
s[0]=m;
t[0]=n;
for(int i=1;i<=m;i++)
s[i]=s1.at(i-1);
for(int j=1;j<=n;j++)
t[j]=t1.at(j-1);
}
/************************************************************************/
//獲取Next值
void GetNext()
{
next = new int[n+1];
next[0]=9999;
int j=1;
int k=0;
next[1]=0;
while(j<(int)(t[0]))
{
if(k==0||t[j]==t[k])
{
++j;
++k;
next[j]=k;
}
else
k=next[k];
}
}
/************************************************************************/
void QuickSort(string str[],int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(str,low,high);
QuickSort(str,low,pivotloc-1);
QuickSort(str,pivotloc+1,high);
}
}
/************************************************************************/
int Partition(string str[],int low,int high)
{
int highcomparepivotkey;
int pivotkeycomparelow;
string tmp=str[low];
while(low<high)
{
highcomparepivotkey=(str[high]).compare(0,sizeof(str[high]),tmp);
if(highcomparepivotkey==0)
highcomparepivotkey=1;
if(highcomparepivotkey==-1)
highcomparepivotkey=0;
while(low < high && highcomparepivotkey)
{
--high;
highcomparepivotkey=(str[high]).compare(0,sizeof(str[high]),tmp);
if(highcomparepivotkey==0)
highcomparepivotkey=1;
if(highcomparepivotkey==-1)
highcomparepivotkey=0;
}
str[low]=str[high];
pivotkeycomparelow=tmp.compare(0,sizeof(tmp),str[low]);
if(pivotkeycomparelow==0)
pivotkeycomparelow=1;
if(pivotkeycomparelow==-1)
pivotkeycomparelow=0;
while(low<high && pivotkeycomparelow)
{
++low;
pivotkeycomparelow=tmp.compare(0,sizeof(tmp),str[low]);
if(pivotkeycomparelow==0)
pivotkeycomparelow=1;
if(pivotkeycomparelow==-1)
pivotkeycomparelow=0;
}
str[high]=str[low];
}
str[low]=tmp;
return low;
}
/************************************************************************/
int GetLength()
{
ifstream fin;
fin.open("G:\\KMP\\yuanshi.txt");
int length=-1;
string b;
do {
fin>>b;
length++;
} while(b!="");
fin.close();
return length;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -