当前位置：文档之家› KMP(next)算法c语言实现

KMP(next)算法c语言实现

/****************************************************************************** *文件名：实验3.c

*文件描述：试编写一程序，实现KMP算法，输入三组主串S和模式串P，输出模式串的*Next(j)函数值，

*以及该P在S中的位置的定位函数值，即序号值。其中S的长度为15~25,P的长度为5~8。*创建人：赵军伟2009.11.15

******************************************************************************/ #include

#include

struct node

{

char data;

struct node *next;

};

struct node* input()

{

struct node *str;

struct node *p,*r;

char x;

int n=0;

/*str=NULL;*/

scanf("%c",&x);

while(x!='\n')

{

n=n+1;

p=(struct node*)malloc(sizeof (struct node));

p->data=x;

p->next=NULL;

if(n==1)

{

str=p;

}

else

{

r->next=p;

}

r=p;

scanf("%c",&x);

}

return str;

}

void Output(struct node * str)

{

struct node*p;

p=str;

while(p!=NULL)

{

printf("%c",p->data);

p=p->next;

}

printf("\n");

}

struct node * LinkStrMatch(struct node *T,struct node *P)

{

struct node *shift,*t,*p;

int i=0;

shift=T;

t=shift;p=P;

while(t&&p)

{

if(t->data==p->data)

{

t=t->next;

p=p->next;

i++;

}

else

{

shift=shift->next;

t=shift;

p=P;

i++;

}

i++;

if(p==NULL)

{

printf("\tKMP success !!!\t The address is %d\n",i-StrLen(P)+1);

return shift;

}

else

{

printf("\tKMP Fail !!!\n");

return NULL;

}

int GetNext(struct node *T)

{

int i=1, j=0,k=0,t;

int tLen = StrLen(T);

char p[100];

char next[100]="";

for(k=0;k<=tLen;k++)

{

p[k]=T->data;

T=T->next;

}

next[1] = 0;

while(i < tLen)

{

if (j ==0 || p[i] == p[j])

{

++i;

++j;

next[i] = j;

}

else

j= next[j];

}

for(t=1 ; t<=StrLen(T); t++)

{

printf(" %d ",next[t]);

}

printf("\n");

return 1;

}

int StrLen(struct node * T)

{

int len=0;

while(T->next!=NULL)

{

T=T->next;

len++;

}

return(len);

}

void main()

{

struct node *T1,*T2,*T3,*P,*C1,*C2,*C3;

int t;

T1=input();

T2=input();

T3=input();

P=input();

GetNext(P);

printf("\t T1: ");

LinkStrMatch(T1,P);

printf("\t T2: ");

LinkStrMatch(T2,P);

printf("\t T3: ");

LinkStrMatch(T3,P);

getch();

}

RC4加密算法C语言实现

RC4 加密算法 C 语言实现代码文件名 RC4.cpp Encrypt.h (代码详见后文) 备注：将以上两个文件放在相同的路径(建议不要放在中文路径下)编译执行！编译环境 Microsoft Visual C++ 6.0 C-Free 5.0 代码解释 RC4 加密算法是大名鼎鼎的RSA 三人组中的头号人物Ron Rivest 在1987 年设计的密钥长度可变的流加密算法簇。之所以称其为簇，是由于其核心部分的S-box 长度可为任意，但一般为256字节。该算法的速度可以达到DES 加密的10倍左右。 RC4 算法的原理很简单，包括初始化算法和伪随机子密码生成算法两大部分。假设S-box 长度和密钥长度均为为n。先来看看算法的初始化部分(用类C伪代码表示)： for (i=0; i

} 得到的子密码sub_k用以和明文进行xor运算，得到密文，解密过程也完全相同。 RC4加密算法在C++中的实现： RC4函数(加密/解密)：其实RC4只有加密，将密文再加密一次，就是解密了。 GetKey函数：随机字符串产生器。 ByteToHex函数：把字节码转为十六进制码，一个字节两个十六进制。十六进制字符串非常适合在HTTP中传输。 HexToByte函数：把十六进制字符串，转为字节码。。 Encrypt函数：把字符串经RC4加密后，再把密文转为十六进制字符串返回，可直接用于传输。 Decrypt函数：直接密码十六进制字符串密文，再解密，返回字符串明文。源代码以下为Encrypt.h文件代码 #ifndef _ENCRYPT_RC4_ #defi ne _ENCRYPT_RC4_ #in clude #defi ne BOX_LEN 256 int GetKey(c onst un sig ned char* pass, int pass_le n, un sig ned char *out); int RC4(c onst un sig ned char* data, int data_le n, const un sig ned char* key, int key_le n, un sig ned char* out, i nt* out_le n); static void swap_byte( un sig ned char* a, un sig ned char* b); char* En crypt(co nst char* szSource, const char* szPassWord); // 加密，返回加密结果 char* Decrypt(co nst char* szSource, con st char* szPassWord); // 解密，返回解密结果 char* ByteToHex(c onst un sig ned char* vByte, const int vLe n); // 把字节码pbBuffer转为十六进制字符串，方便传输 unsigned char* HexToByte(const char* szHex); // 把十六进制字符串转为字节码pbBuffer，解码 #e ndif // #ifndef _ENCRYPT_RC4_

模式匹配的KMP算法详解

模式匹配的KMP算法详解模式匹配的KMP算法详解这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。

补充全排列算法C语言实现

字符串全排列算法C语言实现问题描述：输入一个字符串，打印出该字符串中字符的所有排列。输入: 123 输出: 123 132 213 231 312 321 问题分析：现象分析：这种问题，从直观感觉就是用递归方法来实现即：把复杂问题逐渐简单化，进而得出具体代码实现。（如何发现一个问题可以使用递归方式来解决？经分析可以发现：M 个数的排列方法与N(N>M)个数的排列方法没有区别，处理方法与数据的个数没有关系。处理方法的一致性，就可以采用递归）。 3个数（123）排列，第一位1不动，剩下两个数（23）的排列，只要相互颠倒一下，就可以出现关于1开头的所有排列 123 132 把2换到第一位，保持不动，剩下的两个数（13）的排列，只要相互颠倒一下，就可以出现关于2开头的所有排列 213 231 同理，把3换到第一位，可得到 312 321 扩展：把3个数的所有排列，前面加一个4，就可以得到关于4开头的所有的排列4123 4132 4213 4231 4312 4321 若把4与后续数据中的任意一个数据交换，通过完成对后续三个数的全排列，就可以得到相应的数开头的四数的排列。总结：对4个数的排列，可以转换成首位不动，完成对3个数的排列对3个数的排列，可以转换成首位不动，完成对2个数的排列对2个数的排列，可以转换成首位不动，完成对1个数的排列对于1个数，无排列，直接输出结果算法实现说明：

对n个数的排列，分成两步：（1）首位不动，完成对n-1个数的排列，（2）循环将后续其他数换到首位，再次进行n-1个数的排列注：排列完成后，最终的串要与原串相同 C语言代码实现： #include #include //将串左移一位，首位存到末尾。 void shift( char *s ) { if ( !s||!s[0] ) return ; //security code . null string char ch=s[0]; int i=0; while( s[++i] ) s[i-1]=s[i] ; s[i-1]=ch; } //本函数对于一个已排序好的数据进行全排列 void permutation(char list[], int head ) { int i,len; len=strlen(list) ; if ( len-head == 1 ) //后续没有再排列的，则输出排列数据 { printf( "%s\n", list ); } else { for (i = k; i

模式匹配KMP算法实验报告

实验四：KMP算法实验报告一、问题描述模式匹配两个串。二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：