c4_assistant.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
文学研究助手程序代码
使用KMP算法查找关键字，并用链表存储各行的信息
BY:wangyucao
*/
#include <fstream>
#include <iostream>
#include <cstring>
#include <memory>
#include <iomanip>
#define MAXW 20
//#define cin fin
using namespace std;
ifstream fin("text.in");
ofstream fout("text.out");
struct Node{
	int line,time;
	Node* next;
};
struct LINE{
	int time;
	Node* head;
	Node* tail;
}*Line[MAXW];
char Tline[100];
char keyword[MAXW][25];
int *next[MAXW],line_now;

int* GetNextVal(const char *s, int &len)
{
    len = strlen(s);
    int *next = new int[len];
    int i = 0;
    int j = -1;
    next[0] = -1;
    while(i<len-1)
    {
        if(j==-1 || s[i]==s[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
    return next;
}
/*void get_nextval(int no)
{
	int i,j;
	next[no][0]=-1;
	j=-1;
	for(i=1;i<strlen(keyword[no]);i++)
	{
		while(j>-1 && keyword[no][i]!=keyword[no][j+1]) j=next[no][j];
		if(keyword[no][i]==keyword[no][j+1]) j++;
		next[no][i]=j;
	}
}*/

void KMP_search(char *L,int no)
{
	int i,j,len,m,t=0;
	Node *p;	
	len=strlen(L);
	m=strlen(keyword[no]);
	j=-1;
	for(i=0;i<len;i++)
	{
		while(j>-1 && keyword[no][j+1]!=L[i]) 
			j=next[no][j];
		if(keyword[no][j+1]==L[i])  j=j+1;
		if(j==m-1) 
		{
			if((i-m==0 || (!(L[i-m]<='z' && L[i-m]>='a')&&!(L[i-m]<='Z' && L[i-m]>='A')))&&
			   (i+1>=len || (!(L[i+1]<='z' && L[i+1]>='a')&&!(L[i+1]<='Z' && L[i+1]>='A'))))
			{
				t++;
				j=next[no][j];
			}
		}
	}
 	if(t>0)
	{
		if(Line[no]->head==NULL)
		{
			p=new Node;
			p->line=line_now;
			p->time=t;
			p->next=NULL;
			Line[no]->head=p;
			Line[no]->tail=p;
		}
		else
		{
			p=new Node;
			p->line=line_now;
			p->time=t;
			p->next=NULL;
			if(Line[no]->tail==NULL) Line[no]->tail=p;
			else{
					Line[no]->tail->next=p;
					Line[no]->tail=p;
				}
		}
	}
}
void Output(int n)
{
	Node *p,*q;
	int k;
	for(int i=0;i<n;i++)
	{
		k=-1;
		p=Line[i]->head;
		Line[i]->head=NULL;
		cout<<keyword[i]<<endl;
		while(p!=NULL)
		{
            q=p;            
			cout<<"Line:"<<'\t'<<p->line<<'\t'<<"Times:"<<'\t'<<p->time<<'\t';
			p=p->next;
			delete q;
			k++;
			if((k+1)%2==0) cout<<endl;
		}
		cout<<endl;
		delete Line[i];
		
	}
}
int main()
{  
    int i,j,k,n;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>keyword[i];
	for(i=0;i<n;i++)
	{
		k=strlen(keyword[i]);
		next[i]=GetNextVal(keyword[i],k);
		Line[i]=new LINE;
		Line[i]->time=0;
		Line[i]->tail=NULL;
		Line[i]->head=NULL;
	}
	line_now=0;
	while(!fin.eof())
	{
 		line_now++;
		fin.getline(Tline,sizeof(Tline),'\n');
		for(i=0;i<n;i++)
			KMP_search(Tline,i);
	}
	Output(n);
    return 0;
}