string.cpp

一个简单的数据结构算法,字符串基本匹配算法与模式匹配算法的演示.

// string.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "string"
#include <iostream>
using namespace std;
#include "time.h"
#define max 99999


void show_string_s(char s[],int l);
void show_string_t(char t[],int l);
int m,n;
char *s; char *t;
int *next;

void init_string(string ss,string tt)
{
	cout<<"输入原串S:"<<endl;                //原串
    cin>>ss;
    m=ss.length(); 
	if (s=NULL)
	{
		cout<<"不能分配内存空间"<<endl;
	}
    s=new char[m+1];
    s[0]=m;									//s[0]存放字符串长度
    for(int i=1;i<=m;i++)
	{
		s[i]=ss.at(i-1);
	}


    cout<<"输入模式串T:"<<endl;                //模式串
	cin>>tt;
	n=tt.length();
	if (t=NULL)
	{
		cout<<"不能分配内存空间"<<endl;
	}
    t=new char[n+1];
    t[0]=n;
    for(i=1;i<=n;i++)
    {
		t[i]=tt.at(i-1);
	}
    show_string_s(s,m);
    show_string_t(t,n);
	cout<<endl;
}



void show_string_s(char s[],int l)                  //显示原串
{
	cout<<"原串S为:";
    for(int i=1;i<=m;i++)
    cout<<s[i]<<" ";
    cout<<endl;
    cout<<"长度为: "<<int(s[0])<<"\n";
}


void show_string_t(char t[],int l)                 //显示模式串
{
	cout<<"模式串T为:";
    for(int i=1;i<=n;i++)
    cout<<t[i]<<" ";
    cout<<endl;
    cout<<"长度为: "<<int(t[0])<<"\n";
}


int Index(int pos)                               //简单模式匹配
{
	int i=pos,j=1;
	while (i<=(int)(s[0]) && j<=(int)(t[0]))
	{
		if(s[i]==t[j])
		{
			++i;
			++j;
		}
		else
		{
			i=i-j+2;
			j=1;
		}
	}
		if (j>(int)(t[0]))
		{
			cout<<"匹配位置为:从第"<<pos<<"个位置算起的"<<i-((int)(t[0]))-pos+1<<"个位置"<<endl;
	        cout<<endl;
		}
		else
		{
			cout<<"匹配失败"<<endl;
			cout<<endl;
		}
		return 0;
}



void next_string(char t[],int next[])               //显示next函数
{
    next=new int[n+1];
    int i=1,j=0,x;
	next[0]=9999;
    next[1]=0;
    while(i<=(int)(t[0]))
	{
		if(j==0||t[i]==t[j])
		{
			++i;
			++j;
			next[i]=j;
		}
        else j=next[j];
	}

	cout<<"模式串的next函数值"<<endl;
    for( i=1;i<=n;i++)
	{
		cout<<"next["<<i<<"]="<<next[i]<<"   ";
		x++;
		if (x%5==0)
		{
			cout<<endl;
		}
	}
	cout<<endl;
	cout<<endl;
}



int kmp(int pos,int next[])                  //KMP算法
{
    next=new int[n+1];
    int i=1,j=0;
	next[0]=max;
    next[1]=0;
    while(i<=(int)(t[0]))
	{
		if(j==0||t[i]==t[j])
		{
			++i;
			++j;
			next[i]=j;
		}
        else j=next[j];
	}

    //算法实现


    i=pos,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]))
	{
       cout<<"匹配位置为:从第"<<pos<<"个位置算起的"<<i-((int)(t[0]))-pos+1<<"个位置"<<endl;
	   cout<<endl;
	   return 0;
	}
    else
	{
		cout<<"匹配失败"<<endl;
	    cout<<endl;
	}
	return 0;
}



int main(int argc[],char*args[])
{
	string ss,tt;
	int x,y,pos;
	bool z;
	cout<<"请按对应数字执行操作"<<endl;
	cout<<"输入要执行匹配的字符串: 1"<<"     "<<"退出操作: 2"<<endl;
	cin>>y;
	switch (y)
	{
	case 1:init_string(ss,tt);
		do
		{
			cout<<"开始新的字符串匹配: 1"<<endl;
			cout<<"执行简单模式匹配算法: 2"<<endl;
			cout<<"显示NEXT函数: 3"<<endl;
			cout<<"执行KMP算法: 4"<<endl;
			cout<<"退出操作: 5"<<endl;
			cin>>x;
			switch (x)
			{
			case 1:
				delete []s;
                delete []t;
                delete []next;
				init_string(ss,tt);
				z=1;
				break;
			case 2:
				cout<<"要从第几个位置开始匹配"<<endl;
				cin>>pos;
				Index(pos);
				z=1;
				break;
			case 3:
				next_string(t,next);
				z=1;
				break;
			case 4:
				cout<<"要从第几个位置开始匹配"<<endl;
				cin>>pos;
				kmp(pos,next);
				z=1;
				break;
			case 5:
				z=0;
				break;
			}
		}while (z!=0);
	case 2:
		break;
	}
    delete []s;
    delete []t;
    delete []next;
 return 0;
}