KMP代码
2021/10/22 23:42:45
本文主要是介绍KMP代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
//线性表的使用及函数定义 //KMP算法如果不想了解理论可以看看这个: //https://blog.csdn.net/weixin_46007276/article/details/104372119?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163490584616780264080014%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=163490584616780264080014&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-104372119.pc_search_result_cache&utm_term=kmp%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187 //KMP算法的详细理论视频我放到b站上了,有兴趣看看。: #include<stdio.h> #include<malloc.h> #define _CRT_SECURE_NO_WARNINGS_ #define OK 2 #define ERROR -1 #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define Status int//用数值返回状态,状态值如上所示。 #define ElemType char//串一半都是字符串。 #define InitSize 100 #define IncreaseSize 10 typedef struct str { ElemType* base; int Alllen; int CurLen; }String; //朴素的模式识别算法。 int MortalIndex(String &S,String &T,int pos) { String temp; temp.base = (ElemType*)malloc((T.CurLen) * sizeof(ElemType)); int i = pos; int j = 0; for (i = pos; i < S.CurLen ; i++) { for (j = 0; j < S.CurLen; j++) { if (S.base[i + j] == T.base[j]) j = j; else break; } if (j == S.CurLen) return i; } if (i == S.CurLen) return 0; }//S为目标串,T串为模式串,pos为从第pos位开始进行比较。 //朴素模式匹配算法,其进位为每次加一,会浪费大量的时间。时间复杂度高。回溯次数大,回溯时间长。 //使用CMP算法进行处理 void get_next(String& T, int next[]) { int i = 1;//next的下标,从1开始。 next[i] = 0; next[0] = 999999;//随便一个都可以,无所谓的。我只是不想让这个next[0]是空的,不好看。。。。。。 int k = 0;//k为可以满足条件的最大长度值。 while (i < T.CurLen) { if (k == 0 || T.base[i] == T.base[k]) { i++; k++; next[i] = k; }//如果Pj=Pk或着直接为零,那么,直接加一就行了。 else k = next[k];//当不满足上述条件的时候,直接进行处理,让k取到next【k】。 } } Status Index_CMP(String& S, String& T, int pos) { int* next; get_next(T, next); int i = pos; int k = 1; while (i < S.CurLen && k < T.CurLen) { if (k == 0 || S.base[i] == T.base[k]) { k++; i++; }//如果为0,那么相当于向后移动一位,如果两个相等,向后移动一位是属于正常的现象。 else { k = next[k];//如果匹配失败,直接进入next[k]位置进行匹配与判断。这个时候i是不动的。 } } if (k > T.CurLen) return i - T.CurLen;//现在比到了最后一位。要回到第一位并返回第一位的值。 else return 0;//当k无法大于T串长度时,认为其没有办法完成全部T串的比较。直接失效。 } int main() { return 0; }
这篇关于KMP代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)