/*
正则表示是用来匹配目的串中是否含有正则式的一种方法，对于正则式regexp，目的串test，先定义正则匹配的原则:
c 匹配目的串中的字符
． 匹配任意字符
* 匹配0个或多个此字符的前一个字符
例如： regexp：A． test：ABCD return 1；
regexp：Ab．C test：AbCd return 0；
regexp：A* test：AAAAA return 1；
现在定义一个函数unsigned int ( char * regexp , char * test )，要求写出一个用于正则表达的函数的算法。
*/
/* 匹配方法描述：
对于正则串A和目的串B设立两个标量i，j，建立一个循环结构
i的初始值为1，j的初始值也为1，
读取正则串中的第i个字符a，分为三种情况：
若a为 '.' 匹配任意字符 i++ j++
若a为 '*' 若：目的串中B[j]='\0' 则匹配成功，匹配结束
若：目的串中B[j]!= A[i-1] 匹配失败，重新匹配让j的初始值加1
若：目的串中B[j]=A[i-1] j++ ;继续判断B[j] j++ 继续判断b[j]是否和A[i-1]相等，直到不等或者到达目的串中的最后一个元素,i++,匹配成功。
若a为 某字符 若：目的串中B[j]=A[i] i++ j++
若：目的串中B[j]!=A[i] 匹配失败 重新匹配让j值加1
当i 大于A串的长度时，匹配成功 循环退出
当j 大于B串的长度时，匹配失败 循环退出
如此循环直到碰到循环的出口
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
static int * next;
void InitialNext(const char * regxp)
{
int nextNum = strlen(regxp);
next = (int *)malloc(nextNum*sizeof(int));
}
void GetNext(const char * regxp)//求正则串regxp中的next函数值并存入数组next
{
InitialNext(regxp);
int i = 1;
next[1] = 0;
int j = 0;
int regxpLength = strlen(regxp);
while (i<regxpLength)
{
if (j == 0 || regxp[i] == regxp[j]) { ++i; ++j; next[i]=j; }
else j = next[j];
}
}
unsigned int RegMatch(const char * regxp,const char * test)
{
GetNext(regxp);
int i=0,j=1;
int regLength = strlen(regxp);
int testLength = strlen(test);
while (i<= regxp[0] && j<= test[0])
{
if (j == 0 || regxp[i] == test[j]) { ++i; j++; }
else j = next[j];
}
if (j>testLength) return i - testLength; //匹配成功
else return 0;
}
int main()
{
char * regexp = "A*B";
char * test = "ABBB";
int result=0;
result = RegMatch(regexp,test);
if (result > 0) printf("Match Successfully!\n");
else printf("Match Failed!\n");
return 0;
}
责任编辑：小草
