//函数:int* MakeSkip(char *, int)
//目的:根据坏字符规则做预处理,建立一张坏字符表
//参数:
//ptrn =>模式串P
//PLen =>模式串P长度
//返回:
//int* - 坏字符表
int* MakeSkip(char *ptrn, int pLen)
{
int i
//为建立坏字符表,申请256个int的空间
//PS:之所以要申请256个,是因为一个字符是8位,
// 所以字符可能有2的8次方即256种不同情况
int *skip = (int*)malloc(256*sizeof(int))
if(skip == NULL)
{
fprintf(stderr, "malloc failed!")
return 0
}
//初始化坏字符表,256个单元全部初始化为pLen
for(i = 0i <256i++)
{
*(skip+i) = pLen
}
//给表中需要赋值的单元赋值,不在模式串中出现的字符就不用再赋值了
while(pLen != 0)
{
*(skip+(unsigned char)*ptrn++) = pLen--
}
return skip
}
//函数:int* MakeShift(char *, int)
//目的:根据好后缀规则做预处理,建立一张好后缀表
//参数:
//ptrn =>模式串P
//PLen =>模式串P长度
//返回:
//int* - 好后缀表
int* MakeShift(char* ptrn,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift = (int*)malloc(pLen*sizeof(int))
int *sptr = shift + pLen - 1//方便给好后缀表进行赋值的指标
char *pptr = ptrn + pLen - 1//记录好后缀表边界位置的指标
char c
if(shift == NULL)
{
fprintf(stderr,"malloc failed!")
return 0
}
c = *(ptrn + pLen - 1)//保存模式串中最后一个字符,因为要反复用到它
*sptr = 1//以最后一个字符为边界时,确定移动1的距离
pptr--//边界移动到倒数第二个字符(这句是我自己加上去的,因为我总觉得不加上去会有BUG,大家试试“abcdd”的情况,即末尾两位重复的情况)
while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3
//该do...while循环完成以当前pptr所指的字符为边界时,要移动的距离
do{
while(p1 >= ptrn &&*p1-- != c)//该空循环,寻找与最后一个字符c匹配的字符所指向的位置
p2 = ptrn + pLen - 2
p3 = p1
while(p3 >= ptrn &&*p3-- == *p2-- &&p2 >= pptr)//该空循环,判断在边界内字符匹配到了什么位置
}while(p3 >= ptrn &&p2 >= pptr)
*sptr = shift + pLen - sptr + p2 - p3//保存好后缀表中,以pptr所在字符为边界时,要移动的位置
// PS:在这里我要声明一句,*sptr = (shift + pLen - sptr) + p2 - p3
// 大家看被我用括号括起来的部分,如果只需要计算字符串移动的距离,那么括号中的那部分是不需要的。
// 因为在字符串自左向右做匹配的时候,指标是一直向左移的,这里*sptr保存的内容,实际是指标要移动
// 距离,而不是字符串移动的距离。我想SNORT是出于性能上的考虑,才这么做的。
pptr--//边界继续向前移动
}
return shift
}
//函数:int* BMSearch(char *, int , char *, int, int *, int *)
//目的:判断文本串T中是否包含模式串P
//参数:
//buf =>文本串T
//blen =>文本串T长度
//ptrn =>模式串P
//PLen =>模式串P长度
//skip =>坏字符表
//shift =>好后缀表
//返回:
// int - 1表示成功(文本串包含模式串),0表示失败(文本串不包含模式串)。
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen
if (plen == 0)
return 1
while (b_idx <= blen)//计算字符串是否匹配到了尽头
{
int p_idx = plen, skip_stride, shift_stride
while (buf[--b_idx] == ptrn[--p_idx])//开始匹配
{
if (b_idx <0)
return 0
if (p_idx == 0)
{
return 1
}
}
skip_stride = skip[(unsigned char)buf[b_idx]]//根据坏字符规则计算跳跃的距离
shift_stride = shift[p_idx]//根据好后缀规则计算跳跃的距离
b_idx += (skip_stride >shift_stride) ? skip_stride : shift_stride//取大者
}
return 0
}
Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异的顶点s称为缘。
单源最短路径问题,或者称为最短路径问题,是要确定从s到V中没一个其他
顶点的距离,这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给我了c++下的源代码! --by 伟伟猪
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d
cout<<"input the value of n:"
cin>>n
cout<<endl
d=new int[n]
s=new int[n]
p=new int[n]
w=new int*[n]
for(i=0i<ni++)
for(i=0i<ni++)
for(j=0j<nj++)
cin>>w[i][j]
for(s[0]=1,i=1i<ni++)
{
s[i]=0d[i]=w[0][i]
if(d[i]<infinity) p[i]=0
else p[i]=-1
}
for(i=1i<ni++)
{
t=infinityk=1
for(j=1j<nj++)
if((!s[j])&&(d[j]<t))
s[k]=1//point k join the S
for (j=1j<nj++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
}
cout<<"从源点到其它顶点的最短距离依次如下:"
for(i=1i<ni++) cout<<d[i]<<" "
}
/*********
顶点个数用n表示,这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/
把你的语句搬个家就成了。完整程序如下:#include <stdio.h>
char *Ls(char *s){
int i,b,e,bm,em
bm=em=0
for(i=0s[i])
{
while(s[i]&&s[i]==' ')i++
b=i
while(s[i]&&s[i]!=' ')i++
e=i
if(e-b>em-bm)
{
em=e
bm=b
}
}
s[em]='\0'
return s+bm
}
int main(){
char s[200]
printf("Please input a sentence:\n")
gets(s)
printf("Output:\n")
printf("The longest word is:%s\n",Ls(s))
return 0
}
-------------
函数调用 Ls(s) 返回的是字符串,你可以直接打印,也可以用 strcpy() 存放到一个字符串变量里。