算法题以输入的字符串开头

‘壹’ 数据结构与算法——字符串匹配问题(KMP算法)

KMP算法也是比较着名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：

T = “abcdex”
j 123456
模式串 abcdex
next[j] 011111

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

next数组其实就是求解字符串要回溯的位置
假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};

在求解nextVal数组的5种情况

‘贰’ 经典C语言面试算法题

经典C语言面试算法题

1.写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)

功能：

在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回

9，outputstr所指的值为123456789。

#include

#include

#include

int FindMax_NumStr(char *outputstr,char *inputstr)

{

char *in = inputstr,*out = outputstr,*temp;

char *final;

int count = 0;

int maxlen = 0;

int i;

while(*in!='')

{

if(*in > 47 && *in < 58)

{

for(temp = in;*in> 47 && *in <58;in++)

count++;

}

else

in++;

if(maxlen < count)

{

maxlen = count;

count = 0;

final = temp;

}

}

for(i =0;i

{

*out = *final;

out++;

final++;

}

*out = '';

return maxlen;

}

void main(void)

{

char input[]="abc123def123456eec123456789dd";

char output[50] = {0};

int maxlen;

maxlen = FindMax_NumStr(output,input);

printf("the str %s ",output);

printf("the maxlen is %d ",maxlen);

}

2.求1000!的未尾有几个0;

求出1->1000里,能被5整除的数的个数n1,能被25整除的数的个数n2,能被125整除的'数的个数n3,能被625整除的数的个数n4.1000!末尾的零的个数=n1+n2+n3+n4;

只要是末尾是5的数它乘以一个偶数就会出现一个0，而末尾是0的数乘以任何数也都会出现0

而末尾是0的如果是一个0肯定能被5整除，两个0肯定能被25整数，以此类推3个0就能被5的三次方整除，也就是125

1000!就是1-1000数的相乘，能被5整除的所有数分别乘以一个偶数就会出现这些个的0，而例如100，既能被5整除，也能被25整除，所以就是两个0

1000，既能被5，25，也能被125整除，所以算三个0

例如是10!=1*2*3*4*5*6*7*8*9*10，里面有两个数能被5整除，就是10和5，而

5随便乘以一个偶数就出现一个0，而10乘以其它数也会出现一个0，所以10!会有两个0

#include

#define NUM 1000

int find5(int num)

{

int ret = 0;

while(num%5==0)

{

num/=5;

ret++;

}

return ret;

}

int main(void)

{

int result = 0;

int i;

for(i=5;i<=NUM;i+=5)

result +=find5(i);

printf("the total zero number is %d ",result);

return 0;

}

3。编写一个 C 函数，该函数在一个字符串中找到可能的最长的子字符串，且该字符串是由同一字符组成的。

char * search(char *cpSource, char ch)

{

char *cpTemp=NULL, *cpDest=NULL;

int iTemp, iCount=0;

while(*cpSource)

{

if(*cpSource == ch)

{

iTemp = 0;

cpTemp = cpSource;

while(*cpSource == ch)

++iTemp, ++cpSource;

if(iTemp > iCount)

iCount = iTemp, cpDest = cpTemp;

if(!*cpSource)

break;

}

++cpSource;

}

return cpDest;

}

;