数据结构中字符串的匹配问题

来源:互联网 时间:2016-11-07

【问题描述】对任意输入的一串字符,在某文档中进行匹配,并给出匹配结果。

【测试数据】

(1)输入的一行程序,与源代码匹配,源程序自行选择;

(2)输入的一串字符,在某文本文件中匹配,文本文件自行选择。

#include <stdio.h>

#include "stdlib.h"

#include <iostream>

#include<fstream>

using namespace std;

//宏定义

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define MAXSTRLEN 100

typedef char SString[MAXSTRLEN + 1];

/*

***************

** 字符串的匹配

** @autho 刘辉

** @time 2016年11月7日

***************

*/

int length(SString S) //计算字符数组的长度

{

int i=0;

while(S[i]!='\0')

i++;

return i;

}

/*

***********************************************************************

存放长度change()

1、将字符串的长度存到字符数组的第一个字符位

2、不能返回一个字符数组,定义一个字符指针指向数组,返回指针

3、注意的是长度的类型是int ,这里存到字符数组中之后会进行自动转码

但如果要使用的时候要进行强制类型转化

4、这里我设置的字符数组的长度没有加上首字符的空间

***********************************************************************

*/

char *change(SString S) //将字符的长度存到字符数组的第一个字符位S[0]

{

int i = 0;

char *p;

for(i=length(S);i>=0;i--)

S[i+1] = S[i];

S[0] = length(S)-1;

p = S;

return p;

}

/*

***********************************************************************

算法的实现 index__BF()

1、BF算法,匹配两个字符串,并返回匹配的字符串首字母所在位置

2、这里参数传递进来的方式是,主函数通过字符指针传递给函数的字符数组接收

3、这里要注意判断条件时的强制类型转换

4、要注意最后的判断条件,长度减一后使用

***********************************************************************

*/

int index__BF(SString S,SString T, int pos) //BF算法,匹配两个字符串,并返回匹配的字符串首字母所在位置

{

if (pos <1 || pos > (int)S[0] ) return 0;

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]) return (i - (int)T[0]);

return 0;

}

/*

************************************************************************

求子串next[i]值的算法

1、注意算法的使用

2、这里的if句内包含了很多巧合的实现

/************************************************************************/

void GetNext(SString T, int next[])

{ int j = 1, 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];

}

}

}

/*

***************

KMP算法的具体实现

***************

*/

int KMPindex(SString S, SString T, int pos)

{

if (pos <1 || pos > (int)S[0] ) exit(ERROR);

int i = pos, j =1;

int next[MAXSTRLEN];

GetNext( T, next);

while (i<= (int)S[0] && j <= (int)T[0])

{

if (S[i] == T[j]||j==0) {

++i; ++j;

} else {

j = next[j];

}

}

if(j > (int)T[0]) return i - (int)T[0];

return ERROR;

}

/*

*******************************************************

主函数main()

1、以字符数组保存

2、然后建立指针指向经过change()后的数组。

3、再建立字符数组存放指针指向的内容

4、用数组参与到BF算法中

******************************************************

*/

void main(){

SString S = "abcacdbadab";

//或者用SString S = {'a','b','c','a','c','d','b','a','d','a','b'};

SString S3;

int i = 0;

ifstream in("d:/test.txt"); //文件流读取文件内的字符串

if(!in)

{

cout<<"open file error!"<<endl;

}

while(in) //循环读取数据

{

in.get(S3[i]);

i++;

}

in.close();

S3[i] = '\0';

SString T ;

cout<<"请输入要匹配的字符串:";

cin>>T;

int pos = 0,pos1 = 0,pos2 = 0;

char *p = change(S);

char *q = change(T);

char *k = change(S3);

SString S1,S2,S4;

for(int i=0;i<length(S)+1;i++)

S1[i] = p[i];

for(int i=0;i<length(T)+1;i++)

S2[i] = q[i];

for(int i=0;i<length(S3)+1;i++)

S4[i] = k[i];

pos = index__BF( S1, S2, 1);

pos1 = KMPindex( S1, S2, 1);

pos2 = KMPindex( S3, S2, 1);

cout<<"Pos:"<<pos<<endl;

cout<<"Pos1:"<<pos1<<endl;

cout<<"Pos2:"<<pos2<<endl;

}

 

相关阅读:
Top