int main()
{
char ca
unsigned char ucb
unsigned short usc
ca = 128
ucb =128
usc = ca + ucb
printf("%d\n", usc)
usc = ca + (short)ucb
printf("%d\n", usc)
usc = (unsigned char)ca + ucb
printf("%d\n", usc)
usc = ca + (char)ucb
printf("%d\n", usc)
getchar()
return EXIT_SUCCESS
}
结果是：0， 0， 256， 65280.
这道题最难得部分，莫过于你是否理解c语言中的数据类型转换 。
有个名词“Inerger Promotion"(整型提升）：在算术类型中有这么一种转换，有符号或无符号的char型，short型和Bit-field在做算术运算之前，首先要做整型提升，然后才能参与运算。（其它的一些类型之间的转换，可以参考任何一本c语言书）
①你的KMP代码里很多东西导致KMP算法变慢：1、计算主字符串长度很浪费时间，可以不用计算的，事先开辟一个大空间。
2、new int[len+1]很浪费时间，事先开辟大空间，或者用多级内存管理。
3、delete []next很浪费时间。
②但是①说的不是本质，真正的原因是：KMP的优点是避免重复匹配的记忆功能，缺点是启动慢构造next，这就导致如果要被匹配的主字符串太短（少于1k个字符都算短的）。
而朴素算法启动不需要时间。
③另一方面，你的main中主字符串和匹配字符串没有相似性（只在最后2个字符串才进行了一次大的返回），而KMP的优点就在于处理相似字符串匹配，相似度越高，字符串越长，匹配效果越好。
④我改了下你的代码，增加的主字符串的长度，提高了字符串相似程度，结果就是KMP的时间比朴素算法要好接近30%：
Time to do Index loops is 32.031
Time to do KMP loops is 23.609
⑤代码如下：
#include<time.h>
#include <iostream.h>
#include <string.h>
int Index_BF ( char S [ ], char T [ ], int pos )
{
int i = pos, j = 0
while ( S[i+j] != '\0'&&T[j] != '\0')
if ( S[i+j] == T[j] )
j ++
else
{
i ++j = 0}
if ( T[j] == '\0')
return i
else
return -1
}
void get_nextval(const char *T, int next[])
{
int j = 0, k = -1
next[0] = -1
while ( T[j/*+1*/] != '\0' )
{
if (k == -1 || T[j] == T[k])
{
++j++k
if (T[j]!=T[k])
next[j] = k
else
next[j] = next[k]
}// if
else
k = next[k]
}
}
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1//空指针或空串，返回-1。
static int next[50]
get_nextval(Pattern,next)//求Pattern的next函数值
static int index,i,j
index=i=j=0
for(Text[i]!='\0' &&Pattern[j]!='\0')
{
if(Text[i]== Pattern[j])
{
++i// 继续比较后继字符
++j
}
else
{
index += j-next[j]
if(next[j]!=-1)
j=next[j]// 模式串向右移动
else
{
j=0
++i
}
}
}
//delete []next
if(Pattern[j]=='\0')
return index// 匹配成功
else
return -1
}
int main()//abCabCad
{
int i
char* text= "jegiradCadCegjirjgirjgirjfewijfejifgjadCadCadCadCadCadCadCadCadCadCadCadCadCadCerigjirjgirejgirejigjreigreigjreigjirgjeigjirjgigijirjeihjirhjirjhirjgijerigjir\
fewfjiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergergergregregregergregregergr\
jegiradCadCegjirjgirjgirjfewijfejifgjadCadCadCadCadCadCadCadCadCadCadCadCadCadCerigjirjgirejgirejigjreigreigjreigjirgjeigjirjgigijirjeihjirhjirjhirjgijerigjir\
fewfjiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergergergregregregergregregergr\
jegiradCadCegjirjgirjgirjfewijfejifgjadCadCadCadCadCadCadCadCadCadCadCadCadCadCerigjirjgirejgirejigjreigreigjreigjirgjeigjirjgigijirjeihjirhjirjhirjgijerigjir\
fewfjiadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttcc\
adCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttcc\
adCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttccadCadCadtttcc\
fewieiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeffefiwejfijiwfjiewjfijeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiegirjgirjgirjigjierjgijrighrjigjeigjadCadCadjreigjrijgirejgijreigjerjigejrbababCabCadcadewfewgfgergregegrgergeiwjjgiejijriegjirigjadCadCadtttccc\
adCadCadtttccctctc"
char*pattern="adCadCadtttccctctc"
clock_t start, finish
double duration
//普通匹配算法
cout<<( "Time to do Index loops is ")
start = clock()
for(int k=0k<50000k++)
{
i=Index_BF(text,pattern,1)
}
finish = clock()
duration = (double)(finish - start) / CLOCKS_PER_SEC
cout<<( "%f seconds\n", duration )<<endl
//KMP匹配算法
cout<<( "Time to do KMP loops is ")<<endl
start = clock()
for(int j=0j<50000j++)
{
i=KMP(text,pattern)
}
finish = clock()
duration = (double)(finish - start) / CLOCKS_PER_SEC
cout<<( "%f seconds\n", duration )<<endl
cin>>finish
return 0
}
