学校的课程设计,本来可以简简单单的描述一下就好了。但是这学期不是面向对象了吗?那么为什么不用面向对象来画蛇添足一下呢?笨笨可可捅鼓了到很晚,贴出来做个纪念。
程序说明:
实现对输入的两个字符串,一个主串一个子串...进行模式匹配.check是普通模式匹配,kmpcheck是KMP算法模式匹配.所以会有两个输出结果,理论上两个结果应该是一致的,实际操作中也是一样...反正我试了几组都没出错...程序简单,没写注释,懒一把.
VC++ 6.0下测试通过
源代码:
//CheckString.h
class CheckString
{
char key;
public:
char s[20];
int len;
int viewhead;
int viewend;
void input();
void check(const CheckString &substring);
void kmpcheck(const CheckString &substring);
void viewnext();
};
//main.cpp
#include <iostream.h>
#include "CheckString.h"
void main()
{
CheckString mainstring;
CheckString substring;
cout<<"输入主串:"<<endl;
mainstring.input();
cout<<"输入子串:"<<endl;
substring.input();
cout<<"普通模式匹配算法开始:"<<endl;
mainstring.check(substring);
cout<<"KMP模式匹配算法开始:"<<endl;
mainstring.kmpcheck(substring);
}
//CheckString.cpp
#include<iostream.h>
#include<stdio.h>
#include "CheckString.h"
void CheckString::input()
{
len=0;
while((key=getchar())!='\n')
{
s[++len]=key;
}
}
void CheckString::check(const CheckString &substring)
{
int i=1,j=1;
while(i<=len)
{
if(s[i++]==substring.s[j])
{
j++;
if(j>substring.len)break;
}
else
{
j=1;
}
}
if(j>substring.len)
{
viewhead=i-substring.len;
viewend=viewhead+substring.len-1;
cout<<"满足匹配起始位置:"<<viewhead<<endl;
cout<<"满足匹配结束位置:"<<viewend<<endl<<endl;
}
else
cout<<"没有一样的啊!!"<<endl<<endl;
}
void CheckString::kmpcheck(const CheckString &substring)
{
int i=1,j=1;
int k=0;
int next[20];
next[1]=0;
while(j<substring.len)
if((k==0)||(substring.s[j]==substring.s[k]))
{
j++;
k++;
next[j]=k;
}
else
k=next[k];
cout<<"输出next[]数组:";
for(i=1;i<=substring.len;i++)
cout<<next[i];
cout<<endl;
i=1;j=1;
while((i<=len)&&(j<=substring.len))
if((j==0)||(s[i]==substring.s[j]))
{
i++;
j++;
}
else
j=next[j];
if(j>substring.len)
{
viewhead=i-substring.len;
viewend=viewhead+substring.len-1;
cout<<"满足匹配起始位置:"<<viewhead<<endl;
cout<<"满足匹配结束位置:"<<viewend<<endl<<endl;
}
else
cout<<"没有一样的啊!!"<<endl<<endl;
}
完事儿。^_^