揭秘数算：揭秘数字背后的秘密与技巧

时间：11-09 名人轶事提交错误

大家好，揭秘数算：揭秘数字背后的秘密与技巧相信很多的网友都不是很明白，包括也是一样，不过没有关系，接下来就来为大家分享关于揭秘数算：揭秘数字背后的秘密与技巧和的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！

题目

有一个主串S={a, b, c, a, c, a, b, d}，和一个模式串T={a, b, d}。请查找主字符串中模式字符串的第一次出现。地点。（全部小写字母）

字符串匹配

1、BF算法

这种方法比较暴力。直接从头到尾逐个字符移动，然后比较对应位置的字符。如果对应的位置相等，那么就找到了。只要有一个位置不想等待，那么就去向右移动一个字符，再次循环比较对应的字符。看起来更加直接和暴力。

思路分析1. 分别用指针i 和j 表示主串S 和模式T 中当前等待比较的字符位置。 i 默认值为pos，j 初始值为1。

2、当两个字符串都没有比较到末尾时，即i和j小于等于S和T的长度时，循环操作：

比较S[i] 和T[j]。如果相等，则i和j分别表示字符串中的下一个位置，继续比较后续字符；如果不相等，则指针返回并再次开始匹配。从主字符串的下一个字符串(i=i - j + 2) 开始，然后将其与模式的第一个字符进行比较(j=1)； 3.如果j T.length，则表示模式T中的每个字符串依次与主字符串S匹配。如果连续字符序列相等，则匹配成功，返回模式T中第一个字符的主串S中的字符的序号（i-T.length）；否则匹配失败，返回0；

代码#defineMAXSIZE 40

typedef char 字符串[MAXSIZE+1]； /* 单元0存储字符串的长度*/

/* 生成一个字符串T，其值等于chars */

状态StrAssign(字符串T,char *chars)

{

整数我；

if(strlen(字符)MAXSIZE)

返回错误；

别的

{

T[0]=strlen(字符);

for(i=1;i=T[0];i++)

T[i]=*(字符+i-1);

返回确定；

}

int Index_BF(字符串S, 字符串T,int pos){

//i为主字符串S中当前位置的下标值，如果pos不为1，则从pos位置开始匹配。

int i=pos；

//j用于子串T中当前位置的下标值

整数j=1;

//如果i小于S的长度且j小于T的长度，则继续循环

而（i=S [0] j=T [0]）{

//如果比较的两个字母相等，则继续比较。

如果（S[i]==T[j]）{

我++；

j++;

}别的

{

//如果不相等，则指针返回并再次匹配。

//i 返回最后匹配的第一位的下一位；

//加1，因为子串第一位为1，开始计数；

//添加一个元素为1，从最后一个匹配数字的下一位开始；

i=i-j+2；

//j返回子串T的第一个位置

j=1；

}}

//如果jT[0]，则找到匹配模式

如果（jT[0]）{

//第i个父字符串遍历的位置-模式字符串长度=索引位置

返回i - T[0]；

}别的{

返回-1；

}

//测试代码

整数我；

字符串s1,s2;

StrAssign(s1, "abcdex");

printf("s1 子串是");

StrAssign(s2, "xe");

printf("s2 子串是");

i=Index_BF(s1, s2, 1);

printf("i=%dn",i);在某些情况下，上述BF算法的效率太低，如下图所示：

BF算法的缺点

可以看到，当T位于第41位时，最终匹配成功，期间进行了(50 - 10 + 1) * 10次判断操作。接下来我们就介绍一下RK算法，看看它的效率如何？

2、RK算法

RK算法的核心思想是如何将模式串或者主串拆分后的子串转换成哈希值。由于相同字符串的哈希值相等，因此可以比较子字符串的哈希值，从而减少计算量。

所以字符串匹配的核心思想就是将字母转换成哈希值。

转换“当前字母”-“a”=数字

例如：

a - a=0；

b - a=1；

c - a=2；

d-a=3；

...

就像数字之间有八进制和十进制系统一样，字母之间也有基本系统。

256=2 * 10 * 10 + 5 * 10 + 6 * 1

567=5 * 10^2 + 6 * 10^1 + 7 * 10^0

字母之间的基数是十六进制。我们可以基于此开发一个哈希值算法：

cba="c" * 26 * 26 + "b" * 26 + "a" * 1=c x 26^2 + b x 26^1 + a x 26^0

cba=2 * 26 * 26 + 1 * 26 + 0 * 1=2 x 26^2 + 1 x 26^1 + 0 x 26^0

cba=1378（1378是当前算法下cba的哈希值）

由此，我们首先可以假设主串为{d,b,c,e,d,b}，模式串为{c,c,c}，利用上面的三组一组计算主串十六进制中子字符串的哈希值：

如十六进制字符串图所示，相邻两个子串对应的哈希值计算公式相交，这意味着我们可以使用s[i - 1]来计算s[i]的哈希值。

我们可以先用数字串来帮助我们更好的理解：

完整的数字集合：{0, 1, 2,3, 4, 5, 6, 7, 8, 9}，为十进制，模式串为123，主串为65127451234。

主字符串的所有子字符串

我们比较第三位的127和第四位的274来比较：

s[ i ]=1 x 10^2 + 2 x 10^1 + 7 x 10^0

s[ i + 1 ]=2 x 10^2 + 7 x 10^1 + 4 x 10^0

s[i + 1]=10 x (127 - 1 x 10^2) + 4

s[i + 1]=10 x (s[i] - 1 x 10^2) + 4

s[i + 1]实际上是前面的s[i]减去最高位1 x 10^2，剩下的两位数之和加上4 x 10^0，即4 x 1=4。

综上所述，当模式串长度为m=3，d以10为底时，主串从i=1开始，第一个数字与模式串进行比较，相邻两个子串之间的关系为：

st[i + 1]=(st[ i ] - s[i] x d^(m - 1)) x d + s[i + m]

同理，字符串也可以按照同样的规则计算相邻子串的哈希值公式：

字符串哈希值公式利用上述公式即可得到每个子字符串的哈希值。您可以将所有子字符串与模式字符串进行比较。如果相等，求结果。但是，还需要考虑哈希冲突（字符串和模式字符串哈希值相等，但字符串不同），那么就需要更复杂的哈希算法。当发现冲突时，需要确认两个字符串是否相等。

代码实现//设置十六进制

#定义d 26

//第二次比较检查哈希冲突

int isMatch(char *S, int i, char *P, int m)

{

int是，ip；

for(is=i, ip=0; is!=m ip !=m; is++, ip++)

if(S[is] !=P[ip])

返回0；

返回1；

}

//计算d^(m - 1)的值

int getMaxValue(int m){

整数h=1;

for(int i=0;im - 1;i++){

h=(h*d);

}

返回h；

}

////S 主字符串P 模式字符串

int RK(字符*S, 字符*P)

{

//1. n: 主串长度，m: 子串长度

int m=(int) strlen(P);

int n=(int) strlen(S);

printf("主字符串长度为：%d，子字符串长度为：%dn",n,m);

//一个。模式串的哈希值； St.主串分解子串的Hash值；

无符号整数A=0;

无符号整型St=0；

//2.求子串和主串中第0~m串的哈希值【计算子串和主串0-m的哈希值】

//循环[0,m)获取模式串A的HashValue和主串第一个[0,m)的HashValue

//此时主字符串："abcaadddabceeffccdd"其[0,2)为ab

//此时模式串："cc"

//cc=2 * 26^1 + 2 *26 ^0=52+2=54;

//ab=0 * 26^1 + 1 *26^0=0+1=1;

for(int i=0; i !=m; i++){

//第一次A=0*26+2;

//第二次A=2*26+2;

A=(d*A + (P[i] - "a"));

//第一次st=0*26+0

//第二次st=0*26+1

St=(d*St + (S[i] - "a"));

}

//3.获取d^m-1值（因为经常使用d^m-1基值）

int hValue=getMaxValue(m);

//4.遍历[0,n-m]，判断模式串HashValue A与其他子串的HashValue是否一致。

//如果不一致，则继续获取下一个HashValue

//如果一致，则进行第二次确认，判断两个字符串是否真正相等。不管怎样，哈希值冲突会导致错误。

//注意细节：

//进入循环时，子字符串的哈希值和主字符串[0,m)的哈希值已经获得，可以直接进行第一轮比较；

//哈希值相等后，再次与字符串进行比较，防止哈希值冲突；

// 如果不相等，则用循环之前计算出的st[0]来计算后面的st[1]；

// 比较过程中，并不是一次性解出所有主串和子串的Hash值。相反，s[i] 用于求解s[i+1]。简单来说，就是在比较哈希值的同时，计算哈希值；

for(int i=0; i=n-m; i++){

如果（A==圣）

if(isMatch(S,i,P,m))

//加1的原因，从1开始计数

返回i+1；

St=((St - hValue*(S[i]-"a"))*d + (S[i+m]-"a"));

}

返回-1；

}

//测试代码

char *buf="abcababcabx";

char *ptrn="abcabx";

printf("主字符串是%sn",buf);

printf("子字符串是%sn",ptrn);

int 索引=RK(buf, ptrn);

printf("查找索引： %dn",index); RK算法比较哈希值，同时计算哈希值。计算量没有BF算法那么多，理解起来可能有点混乱。

3、KMP算法

由于BF算法需要的比较次数最多，因此从前往后移动时的每次比较都需要从模式字符串的第一个字符开始。那么有没有更多的方法来减少比较次数呢？接下来，我们将使用几种不同的模式字符串来分析KMP算法的优点。

情况一

当模式字符串中的所有字符都彼此不同时：

没有重复字符的模式字符串

本例中，如果按照BF算法计算，每次都需要j=6才能知道失配情况。即从左到右遍历主字符串，每次比较都需要从模式串的第一个字符开始，但显然a与模式串中其余的字符不同，所以是如果i在[1, 5]范围内则不需要进一步比较，可以直接从i=6开始继续遍历比较。

情况2

当模式字符串中存在相同字符时，例如：

模式串有重复字符，从左到右遍历。当i在[1, 4]范围内时，模式串比较下标j需要从1开始，即j=1；当i=5时，由于S[4]=T[1]，那么可以从j=2开始比较，发现S[5]=T[2]；同样当i=6时，由于S[4]=T[1]且S[5]=T[2]，所以S[6]可以直接与T[3]进行比较，即当i=6时， j=3，这也减少了比较次数。

综上，我们可以将T字符串每个位置上j值的变化定义为一个next数组，那么next的长度就是T字符串的长度：

next 和j 的关系是，情况1 中的T=abcdex 对应next[j]=011111。这是怎么来的呢？

当j=1时，next[1]=0。当j=2时，j在1到j-1范围内只有字符“a”，属于其他情况。下一个[2]=1；当j=3时，j在1到j-1范围内有字符“ab”。显然a不等于b，属于其他情况。下一个[3]=1；当j=4时，j从1到j-1的范围内有字符“abc”。显然abc不相等，所以属于其他情况。下一个[4]=1；当j=5时，j从1到j-1的范围内有字符“abcd”。显然abcd不相等，所以属于其他情况。案例下一个[5]=1；当j=6时，j从1到j-1的范围内有字符“abcde”。显然abcde不相等，所以属于其他情况next[6]=1；

同理，情况2中的T=abcabx 对应next[j]=011123：

当j=1时，next[1]=0。当j=2时，j在1到j-1范围内只有字符“a”，属于其他情况。下一个[2]=1；当j=3时，j在1到j-1范围内有字符“ab”。显然a不等于b，属于其他情况。下一个[3]=1；当j=4时，j从1到j-1的范围内有字符“abc”。显然abc不存在相等情况，属于其他情况next[4]=1;当j=5时，j从1到j-1的范围内都存在字符“abca”，显然abca的前缀字符“a”和后缀字符“a”是相等的；（因为"p1.pk-1"="pj-k+1 . pj-1"，所以我们得到p1=p4）因此，可以推断k的值为2；因此下一个[5]=2；当j=6时，j从1到j-1的范围内有字符“abcab”。显然，abcab的前缀字符“ab”等于后缀字符“ab”；（因为"p1.pk-1"="pj-k+ 1 . pj-1"，得到[p1, p3-1]=[p6-3+1,p5] ）推导出k 的值为3，所以next[6]=3；结论：如果前缀和后缀等于一个字符k 值为2，两个相等的字符为3；那么n个相等的k值是n + 1。

我们还可以举几个例子：

T={ababaaaba}==下一个[j]=[011234223]

相同的后缀有[empty,empty,empty,a,ab,aba,a,a,ab]

空表示j从1到j-1的范围内没有重复的字符，需要从j=1处开始比较。

T={aaaaaaaab}==下一个[j]=[012345678]

相同的后缀是[空、空、a、aa、aaa、aaaa、aaaaa、aaaaaa、aaaaaaa]。

我们还可以通过以下方法来验证上述结论：

情况1，T=“abcdex”，next[j]=011111；

验证1默认next[1]=0；

i=0,j=1开始遍历；

比较T[ i ] !=T[ j ] ，但i=0，这意味着[a] 只能从[0, 1] 范围内的位置1 开始；

j++,i++ ，所以i=1，j=2；

更新下一个[j]=i;然后下一个[2]=1；

验证2比较T[i] !=T[j]所以将i的位置移回a后面，则i=next[i];那么i=下一个[i]=下一个[1]=0；

此时，[0, 2]范围内是否存在相等的字符；

那么由于i=0，此时的next[j]仍然从第一个位置的字符开始比较；

i++，j++；下一个[j]=下一个[3]=1;

验证比较[1, 3]中是否有相等的字符；

T[i] !=T[j]，所以i的位置往后退；

我=下一个[i]=0;此时i=0；

验证4个比较范围[0, 3]中是否出现相同符号；因为出现i=0，所以字符串比较需要从头开始；我++，j++； i=1，即=4；下一个[j]=i ;下一个[4]=1；

验证5、比较[1, 4]范围内是否有相等的字符；那么T[i] !=T[j]，所以i=next[i]=next[1]=0，回溯

验证6 比较[0, 4]范围内是否出现相同的字符；因为i=0，所以字符串必须从头开始，然后i++,j++,i=1,j=5；下一个[j]=i，下一个[5]=1；

…………

直到最后一个j=6，模式串已经被处理完毕，循环退出。同样的验证方法可以用来验证T=“abcabx”，可以总结为以下规则：

默认下一个[1]=0； i=0,j=1开始遍历；当j S.length j遍历字符串从1到length时；如果i=0，则说明在这个范围[i,j]字符中没有找到相同的值，所以i需要回溯到1的位置；表示下一个[j]=i；如果当T[i]=T[j]相等时，说明找到了同一个字符的位置，所以next[j]=i；当以上两个条件都不满足时，i就会回溯到之前记录的next[i]的位置。代码实现//准备代码

#include "字符串.h"

#include "stdio.h"

#include "stdlib.h"

#定义确定1

#定义错误0

#定义真1

#定义假0

#define MAXSIZE 100 /* 初始分配存储空间*/

typedef int 状态； /* Status为函数的类型，其值为函数结果状态码，如OK等*/

typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */

typedef char 字符串[MAXSIZE+1]； /* 单元0存储字符串的长度*/

//----字符串相关操作---

/* 生成一个字符串T，其值等于chars */

状态StrAssign(字符串T,char *chars)

{

整数我；

if(strlen(字符)MAXSIZE)

返回错误；

别的

{

T[0]=strlen(字符);

for(i=1;i=T[0];i++)

T[i]=*(字符+i-1);

返回确定；

}

状态清除字符串（字符串S）

{

S[0]=0;/* 令字符串长度为零*/

返回确定；

}

/* 输出字符串T。 */

无效StrPrint（字符串T）

{

整数我；

for(i=1;i=T[0];i++)

printf("%c",T[i]);

printf("n");

}

/* 返回字符串中元素的个数*/

int StrLength(字符串S)

{

返回S[0]；

}

//----KMP模式匹配算法---

//1.通过计算返回子串T的下一个数组；

//注意字符串T[0]是存储的字符串的长度；真实的字符内容从T[1]开始；

无效get_next（字符串T，int *下一个）{

整数i,j;

j=1；

我=0;

下一个[1]=0;

//abcdex

//遍历T个模式串，此时T[0]为模式串T的长度；

//printf("长度=%dn",T[0]);

while (jT[0]) {

//printf("i=%d j=%dn",i,j);

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

//T[i]代表后缀的单个字符；

//T[j]表示前缀的单个字符；

++我；

++j；

下一个[j]=i;

//printf("下一个[%d]=%dn",j,下一个[j]);

}别的

{

//如果字符不相同，则回溯i值；

我=下一个[i]；

}

//输出下一个数组值

void NextPrint(int next[],int length)

{

整数我；

for(i=1;i=长度；i++)

printf("%d",下一个[i]);

printf("n");

}

整数计数=0；

//KMP匹配算法(1)

//返回子串T在主串S中pos字符之后的位置，如果不存在则返回0；

int Index_KMP(字符串S,字符串T,int pos){

//i是主串当前位置的下标，j是模式串当前位置的下标

int i=pos；

整数j=

1; //定义一个空的next数组; int next[MAXSIZE]; //对T串进行分析,得到next数组; get_next(T, next); count = 0; //注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度; //若i小于S长度并且j小于T的长度是循环继续; while (i<= S[0] && j<= T[0]) { //如果两字母相等则继续,并且j++,i++ //这里回溯的是j ，所以当j = 0 是，需要i ++ , j ++ ; //第一个字符不匹配时候 j 就回溯了，j = next[1] = 0, if(j == 0 || S[i] == T[j]){ i++; j++; }else{ //如果不匹配时,j回退到合适的位置,i值不变; j = next[j]; } } if (j >T[0]) { return i-T[0];//就是与 T[1] 对应的位置下标 }else{ return -1; } } // 测试嗲吗 //KMP算法调用 StrAssign(s1,"abcababca"); printf("主串为: "); StrPrint(s1); StrAssign(s2,"abcdex"); printf("子串为: "); StrPrint(s2); Status = Index_KMP(s1,s2,1); printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] n",Status);Index_KMP方法的while中，我们可以设置一个主串，一个模式串走一下过程： next数组 01111 主串 abccabcceabc 模式串 abcce i = 1 j = 1 =>S[1] = T[1] =>i++ j++ i = 2 j = 2 =>S[2] = T[2] =>i++ j++ i = 3 j = 3 =>S[3] = T[3] =>i++ j++ i = 4 j = 4 =>S[4] = T[4] =>i++ j++ i = 5 j = 5 =>S[5] != T[5] =>j = next[5] = 1 i = 6 j = 2 =>S[6] = T[1] =>i++ j++ i = 7 j = 3 =>S[7] = T[2] =>i++ j++ i = 8 j = 4 =>S[8] = T[3] =>i++ j++ i = 9 j = 5 =>S[9] = T[4] =>i++ j++ i = 10 j = 6 >T[0] = 5 结束

KMP优化

当然，KMP算法还有优化的空间。例如主串 S = "aaaabcde" ,模式串 T ="aaaaax" . 数组next 为 012345 ; 当我们按上面的算法进行的话，还存在多余进行的步骤。当i = 5, j = 5， S[5] != T[5]，需要回溯，j = next[5] = 4;当i = 5, j = 4， S[5] != T[4]，需要回溯，j = next[4] = 3;当i = 5, j = 3， S[5] != T[3]，需要回溯，j = next[3] = 2;当i = 5, j = 2， S[5] != T[2]，需要回溯，j = next[2] = 1;当i = 5, j = 1， S[5] != T[1]，需要回溯，j = next[1] = 0;此时i++, j++ ;i = 6, j = 1;按上面的算法需要一步一步递减，直到 i = 5 , j = 1 ,继续对比。其实，在比较过程中发现，这2, 3, 4, 5 步骤的回溯比较都是多余的判断。由于T串第2 ，3 ，4，5 位置都是 ‘a’ ,那么可以用next[1] 的值取代后面几个next[j]的值。则优化过的 nextVal = {0, 0, 0, 0, 0, 5} 同理：如果T = “ababaaaba” ,则 next= {011234223}, 优化过的nextVal = {010104210}。当 j = 1, nextVal[1] = 0;当 j = 2, 因为第二个字符“b” 的next值为1，而且第一个字符是"a",不想等，所以nextVal[2] = next[2] = 1;当 j = 3，因为第3个字符“a” 的next值为1，所以与第一位的"a"比较相等，所以nextVal[3] = nextVal[1] = 0;当 j = 4, 因为第4个字符“b” 的next值为2，所以与第二位的“b”比较相等，所以nextVal[4] = nextVal[2] = 1;当 j = 5，next值为3，第5位字符“a” 与第3位字符"a"相等，则nextVal[5] = nextVal[3] = 0;当 j = 6，next值为4, 第6位字符“a”与第4位字符“b”不相等，所以nextVal[6] = 4; .........所以，可总结为以下规律：默认nextVal[1] = 0;T[i] = T[j] 且 ++i, ++j 后 T[i] 依旧等于 T[j] 则 nextVal[i] = nextVal[j];i = 0，表示从头开始i ++, j++后，且T[i] != T[j] 则 nextVal = j;T[i] == T[j]，且 i++, j++后 T[i] != T[j], 则nextVal = j;当T[ii] != T[j] 表示不相等，则需要将 i 退回到合理位置，则i = next[i];void get_nextVal(String T,int *nextVal){ int i,j; j = 1; i = 0; nextVal[1] = 0; while (j< T[0]) { if (i == 0 || T[i] == T[j]) { ++j; ++i; //如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值 if(T[i] != T[j]) nextVal[j] = i; else //如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置 nextVal[j] = nextVal[i]; }else{ i = nextVal[i]; } }