C语言如何实现KMP字符串匹配？
shit
#include #include #include using namespace std; inline void NEXT(const string& T,vector& next) { //按模式串生成vector,next(T.size()) next[0]=-1; for(int i=1;i=0 ) j=next[j] ; //递推计算 if(T[i]==T[j+1])next[i]=j+1; else next[i]=0; // } } inline string::size_type COUNT_KMP(const string& S, const string& T) { //利用模式串T的next函数求T在主串S中的个数count的KMP算法 //其中T非空， vector next(T.size()); NEXT(T,next); string::size_type index,count=0; for(index=0;index Length(t) then index := i - Length(t); end; End; BEGIN ClrScr;{清屏，可不要} Write(‘s = ’); Readln(str_s); Write(‘t = ’); Readln(str_t); int_i := index( str_s, str_t ); if int_i 0 then begin Writeln( 'Found' , str_t,' in ', str_s, 'at ', int_i,' .' ); end else Writeln( 'Cannot find ', str_t,' in' , str_s, '. '); END. index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0
#include <stdio.h>
#include <stdlib.h>
void KmpNextArray(const char* str, int len, int* next) {
/**/if (str == NULL || next == NULL || len <= 0) {
/**//**/return;
/**/}
/**/int n = 1;
/**/int i = 1;
/**/next[0] = 0;
/**/while (i < len && str[i] != str[0]) {
/**//**/next[i++] = 0;
/**/}
/**/if (i >= len) {
/**//**/return;
/**/}
/**/next[i++] = 1;
/**/for (; i < len; i++) {
/**//**/if (str[i] == str[n]) {
/**//**//**/next[i] = ++n;
/**//**/}
/**//**/else {
/**//**//**/next[i] = 0;
/**//**//**/n = 0;
/**//**/}
/**/}
}
int Strlen(const char* str) {
/**/if (str == NULL) {
/**//**/return 0;
/**/}
/**/int n = 0;
/**/while (str[n] != '\0') {
/**//**/++n;
/**/};
/**/return n;
}
const char* KmpFind(const char* str, const char* findstr) {
/**/if (NULL == str || NULL == findstr) {
/**//**/return NULL;
/**/}
/**/int slen = Strlen(str);
/**/if (0 == slen) {
/**//**/return NULL;
/**/}
/**/int flen = Strlen(findstr);
/**/if (0 == flen) {
/**//**/return NULL;
/**/}
/**/if (flen > slen) {
/**//**/return NULL;
/**/}
/**/int* next = (int*)malloc(sizeof(int) * flen);
/**/if (NULL == next) {
/**//**/return NULL;
/**/}
/**/KmpNextArray(findstr, flen, next);
/**/const char* p = str;
/**/int n = 0;
/**/while (p < str + slen) {
/**//**/if (findstr[n] == *p) {
/**//**//**/if (++n >= flen) {
/**//**//**//**/free((void*)next);
/**//**//**//**/return p - n + 1;
/**//**//**/}
/**//**//**/else {
/**//**//**//**/++p;
/**//**//**/}
/**//**/}
/**//**/else if (n > 0) {
/**//**//**/n = next[n - 1];
/**//**/}
/**//**/else {
/**//**//**/++p;
/**//**/}
/**/}
/**/free(next);
/**/return NULL;
}
int main(int argc, char* argv[]) {
/**/char a[100] = { 0 };
/**/char b[100] = { 0 };
/**/fgets(a, 100, stdin);
/**/fgets(b, 100, stdin);
/**///a b均带有换行符
/**/int alen = Strlen(a) - 1;
/**/int blen = Strlen(b) - 1;
/**/a[alen] = '\0';
/**/b[blen] = '\0';
/**/const char* p = KmpFind(a, b);
/**/if (NULL != p) {
/**//**/printf("%s %8d
", a, alen);
/**//**/for (int i = 0; i < (int)(p - a); i++) {
/**//**//**/putchar(' ');
/**//**/}
/**//**/printf("%0.*s %*d
", blen, p, 8 + alen - (int)(p - a) - blen, (int)(p - a));
/**/}
/**/else {
/**//**/printf("No string found!
");
/**/}
/**/return 0;
}
运行截图
kmplayer播放语言设置
解决这个问题的方法如下：1、首先，打开KMPlayer进入界面。2、鼠标右击播放界面，我们在选项卡中选择“language”的选项。3、随即，在language的语言列表中选择“Chinesesimp.ini”。4、然后界面即可设置为简体中文的界面，这样问题就解决了。
c语言 请问输入一个字符串s1和另一个字符串s2如果s1包含s2输出YES否则...
include <stdio.h> include <string.h> void main(){ char s1[20],s2[20];printf("请输入字符串s1,s2\\n");scanf("%s%s",s1,s2);if(strstr(s1,s2)!= NULL){ printf("YES");} else { printf("NO");} system("pause");} 有些有用的函数得知道，不一定记住，但是用的时候能查到...
我的KMP算法做出来了,可是居然运行时间比普通匹配还慢??求高手解答...
i=KMP(text,pattern); } finish = clock(); duration = (double)(finish - start) \/ CLOCKS_PER_SEC; cout<<( "%f seconds\\n", duration )<<endl;return 0;}要求是实现字符串匹配的简单匹配算法和KMP算法,并且使用相同的比较字符串重复比较至少5000次,计算两者的时间差别。请使用C语言。 展开 我...
数据结构用什么语言
问题二:学习数据结构都使用什么语言 自己熟悉什么编程语言 就找一本相应编程语言的数据结构书记进行学习 这样更容易学一些 问题三:数据结构 各编程语言是通用的吗? 数据结构是一种工具,重要的是它的思想。具体的实现倒是没什么的,JAVA和C无非是长的不太一样(只谈语言代码)。算法和数据结构都是一样的东西,《...
C语言的KMB算法中涉及到真子串,请问什么是真子串?
没有KMB算法，只有KMP算法。1、串的定义 串( string)是由零个或多个字符组成的有限序列 记作s=“a1a2…an”其中s为串的名字用成对的双引号括起来的字符序列为串的值但两边的双引号不算串值不包含在串中。ai(1≤i≤n)可以是字母、数字或其它...
kmp如何自动加载英文字幕
），即【ENG ZHCC ZH CHI CHS GB GB2312】。同时点击【常规】选项卡，不要勾选【在屏幕的顶端显示第二组语言类\/开启第二组字幕】即可！注：以上为2.9.3.1428版本KMP菜单，不同版本KMP设置菜单中略有翻译上的差别，如（KMP版本：2.9.3.1214）对应选项翻译成 ：【字幕处理】－【组合字幕|其它...
C语言输入一个句子再输入一个单词 输出单词在句子中的位置 如果单词不...
intKMP(stringW,stringT){ inti=1,j=1;while(i<=n){ while(j!=0&&W[j]!=T[i]){ j=next[j];} if(j==m){ return i-m+1;\/\/success,returnthefirstmatchposition } else{ j++;i++;} } return-1;\/\/failure }\/\/正文串T，匹配串W ...
c语言表示任意字符的方法
任意字符可以用1字节ASCII值表示。你可以确定它的范围（例如，基本ASCII 0x20-0x7e)，然后用循环语句遍历这些字符。char s[]="acdh";然后 给 s[2] 循环语句遍历赋值，组合出 字符串。用你的判据决定 最大。
求助,关于c语言的单词输出程序
将每个单词首字符的地址指针用来链表记录，这样就可以用单词去比较用户输入的一长串字母；但不能将时间复杂度缩小到O(n)；3.综合kmp和Shift-And算法，采取位滑动，和位映射结合的方法；时间复杂度能降低，但...仍然不能从O(n2)降到O(n)所以，开线程是最好达到目的的实现方法；...
关于数据结构的问题,用C语言描述
可能进行的考查方式是:求next和nextval数组值,根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。第四章 数组与广义表学过程序语言的朋友,数组的概念我们已经不是第一次见到了,应该已经“一回生,二回熟”了,所以,在概念上,不会存在太大障碍。但作为考研课程来说,本章的考查重点可能与大学里的...
连怎槟榔： #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define MAX_LEN_OF_STR 30 // 字符串的最大长度 typedef struct String // 这里需要的字符串数组,存放字符串及其长度{ char str[MAX_LEN_OF_STR]; // 字符数组 ...
霍州市19440946293： KMP算法的C语言程序 - ？
连怎槟榔： #include ＂iostream＂#include ＂stdlib.h＂#include ＂stdio.h＂#include ＂malloc.h＂#define MAXSTRLEN 100#define OK 1#define NULL 0 using namespace std; typedef char SString[MAXSTRLEN+1]; SString T,S; int next[MAXSTRLEN],c[...
霍州市19440946293： C语言 KMP算法？
连怎槟榔： 其基本思想是:每当匹配过程中出现字符串比较不等时,不需回溯i指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较. #include <stdio.h> #include <string.h> int index_KMP(char *s,char *t,...
霍州市19440946293： 谁有KMP算法的C语言实现啊 - ？
连怎槟榔： #include<stdio.h>#include<malloc.h>#include<string.h>#include<assert.h>#include<stdlib.h> void getNext(const char * t,int * Next)//get the Next array { int k=-1; int j=0; int size=strlen(t); Next[0]=-1; while(j<size) { if(k==-1||t[j]==t[k])//if k==-1 there are ...
霍州市19440946293： 请会编程的同学帮忙用c语言写一个无回溯模式匹配,kmp算法.. - ？
连怎槟榔： #include#include char a[101],b[101]; int p[101]; int m,n; int main(){ int i,j,k; cin>>a>>b; n=strlen(a); m=strlen(b); p[0]=-1; j=-1; for(i=1;i while(j>=0 && b[j+1]!=b[i]) j=p[j]; if(b[j+1]==b[i]) j=j+1; p[i]=j; } j=-1; for(i=0;i while(j>=0 && b[j+1]!=a[i]) j=p[j]; if(b[j+1]==a...
霍州市19440946293： 在主字符串中查找子串的KMP算法?和字符串中查找字符用KMP算法的C语言代码 - ？
连怎槟榔： /***KMP算法是对蛮力算法的优化,原理很简单.但存在最坏情况,时间复杂度很可能会崩坏到O(m+n). * 推荐在高频度数据查找采用优化的Boyer-Moore算法. *以下为代码 ***/ /***首先创建一个ADT,这里给出最简形式,省略部分涉及不到的...
霍州市19440946293： 数据结构(c语言)版kmp算法next函数怎么算 - ？
连怎槟榔： 模式串用Kmp算法和自己匹配就行了..参见《柔性字符串匹配》
霍州市19440946293： 这个模式匹配怎么做?没头文件,怎样编辑头文件呢? 串KMP算法的C语言实现: #include - ？
连怎槟榔： /*把两个函数直接都放在头文件中,只在写一个主函数,如:*/#include #include ＂sqstring.h＂ void main() { SqString s,t; StrAssign(s,＂ababcabcacbab＂); StrAssign(t,＂abcac＂); printf(＂s:＂);DispStr(s); printf(＂t:＂);DispStr(t); printf(＂位...
霍州市19440946293： 《数据结构(C语言版)》之“串的模式匹配算法” - ？
连怎槟榔： # include <string.h> # include <stdio.h> # include <stdlib.h> # define OK 1 # define ERROR 0 typedef int Status; //串的定长顺序存储结构 # define MAX_STR_LEN 40 typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度 Status ...
霍州市19440946293： 急!!急!!急!!数据结构(C语言版)程序设计题: 使用KMP算法实现一个模式匹配. - ？
连怎槟榔： #include <cstring> #include <iostream> using namespace std; //修正后的求next数组各值的函数代码 void get_nextval(char const* ptrn, int plen, int* nextval) {int i = 0; //i是从0开始的 nextval[i] = -1;int j = -1;while( i < plen-1 ){if( j == -1 || ptrn[i] ==...
