#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;
}