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