KMP序列匹配算法的一个实现原理问题，采用C语言方式的编程计算

Problem Description
When the problem to match S string in T string is mentioned, people always put KMP, Aho-Corasick and Suffixarray forward. But Mr Liu tells Canoe that there is an algorithm called Burrows–Wheeler Transform(BWT) which is quite amazing and high-efficiency to solve the problem.
But how does BWT work to solve the matching S-in-T problem? Mr Liu tells Canoe the firstly three steps of it.
Firstly, we append the ‘\$’ to the end of T and for convenience, we still call the new string T. And then for every suffix of T string which starts from i, we append the prefix of T string which ends at (i – 1) to its end. Secondly, we sort these new strings by the dictionary order. And we call the matrix formed by these sorted strings Burrows Wheeler Matrix. Thirdly, we pick characters of the last column to get a new string. And we call the string of the last column BWT(T). You can get more information from the example below.

Then Mr Liu tells Canoe that we only need to save the BWT(T) to solve the matching problem. But how and can it? Mr Liu smiles and says yes. We can find whether S strings like “aac” are substring of T string like “acaacg” or not only knowing the BWT(T)! What an amazing algorithm BWT is! But Canoe is puzzled by the tricky method of matching S strings in T string. Would you please help Canoe to find the method of it? Given BWT(T) and S string, can you help Canoe to figure out whether S string is a substring of string T or not?

Input
There are multiple test cases.
First Line: the BWT(T) string (1 <= length(BWT(T)) <= 100086).
Second Line: an integer n ( 1 <=n <= 10086) which is the number of S strings.
Then n lines comes.
There is a S string (n * length(S) will less than 2000000, and all characters of S are lowercase ) in every line.

Output
For every S, if S string is substring of T string, then put out “YES” in a line. If S string is not a substring of T string, then put out “NO” in a line.

Sample Input
gc\$aaac
2
aac
gc

Sample Output
YES

NO

Problem Description Clairewd is a member of FBI. After several years concealing in BUPT, she intercepted some important messages and she was preparing for sending it to ykwd. They had agreed that each letter of these messages would be transfered to another one according to a conversion table. Unfortunately, GFW(someone's name, not what you just think about) has detected their action. He also got their conversion table by some unknown methods before. Clairewd was so clever and vigilant that when she realized that somebody was monitoring their action, she just stopped transmitting messages. But GFW knows that Clairewd would always firstly send the ciphertext and then plaintext(Note that they won't overlap each other). But he doesn't know how to separate the text because he has no idea about the whole message. However, he thinks that recovering the shortest possible text is not a hard task for you. Now GFW will give you the intercepted text and the conversion table. You should help him work out this problem. Input The first line contains only one integer T, which is the number of test cases. Each test case contains two lines. The first line of each test case is the conversion table S. S[i] is the ith latin letter's cryptographic letter. The second line is the intercepted text which has n letters that you should recover. It is possible that the text is complete. Hint Range of test data: T<= 100 ; n<= 100000; Output For each test case, output one line contains the shorest possible complete text. Sample Input 2 abcdefghijklmnopqrstuvwxyz abcdab qwertyuiopasdfghjklzxcvbnm qwertabcde Sample Output abcdabcd qwertabcde

C语言程序，运行时KMP算法为什么比BF算法要慢？

next数组使用的是优化过后的数组，网上大部分算法都计算第一次出现的位置，没有计算一共出现多少次，求大神们给个写法

1. 使用KMP算法求出模式p=”aabcaabbaa”的优化后的next数组。注意：只列出数字，数字之间用空格分隔。比如：0 0 0 0 0 0 0 0 0 0 2.利用上题p=”aabcaabbaa”优化后的Next数组，对t=”aaabaabcabaabcaabbaab”进行匹配。有多少次字符比较？（注意：每一次p中的字符与t中的字符的一次比较计做一次）

nextval函数求KMP算法 运行的结果不对，但是我对比了好久却根本找不出到底是哪里错了，跪求 ！！！ #include <stdio.h> #include <string.h> char s[51],t[11]; int next[11]; void get_nextval(char* t,int next[]) { int i=0; int j=-1; int aa=strlen(t); next[0]=-1; while(i<aa) { if(j==-1||t[i]==t[j]) { ++i;++j; if(t[i]!=t[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; } } int index_KMP(char *s,char *t,int pos) { int i=pos; int j=-1; int aa=strlen(t),bb=strlen(s); while(i<bb&&j<aa) { if(j==-1||s[i]==t[i]) { ++i;++j; } else j=next[j]; } if(j>=aa) return i-aa; else return 0; } int main() { //输入主串s,输入子串t,输入开始查找的位置pos，调用get_nextval函数，调用index_KMP函数，输出判断“串s包含串t！”或"串s不包含串t！n" int pos,in; gets(s); gets(t); get_nextval(t,next); scanf("%d",&pos); index_KMP(s,t,pos); in=index_KMP(s,t,pos); if(in!=0) printf("串s包含串t！位置：%d\n",in); else printf("串s不包含串t！\n"); return 0; }

KMP算法 时间复杂度问题

void GetNext(char* p,int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } } 为什么这个算法的时间复杂度是o(模式串长)？ 如果每一个k都要等于next[k]等于k-1？

KMP算法中的前缀函数问题

KMP算法的next函数怎么理解?

kmp算法，可以加快找字串位置的速度。 为什么加快呢，因为在每次比较过程中，找到了模式串对称的小串，然后直接移过去。 比如，主串abcabcabe,模式串abcabe。 第一次，匹配到主串的第二个c，失败，然后根据前面串的对称串ab， 第二次首先匹配第二个ab的首位置。 我的疑问是，跳过中间的字符匹配，会不会造成误差呢？比如少了些匹配成功的机会

#include<stdio.h> #include<stdlib.h> #define MAXSIZE 20 char *String_Create() { char *s,ch; int i=0; s=(char *)malloc(sizeof(MAXSIZE)); ch=getchar(); while(ch!='\n') { *(s+i)=ch; i++; ch=getchar(); } return s; } int String_Length(char *s) { int l=0; while(*s!='\0') { l++; s++; } return l; } int String_IndexKMP(char *d,char *s,int pos) { int i=pos,j=1,ld,ls; ld=String_Length(d); ls=String_Length(s); int k=1,next[20],l=0; next[1]=0; while(k<ls) { if(l==0||(s+k)==(s+l)) { ++k; ++l; if((s+k)!=(s+l)) next[k]=l; else next[k]=next[l]; } else l=next[l]; } while(i<=ld&&j<=ls) { if(j==0||(ld+i)==(ls+j)) { ++i; ++j; } else j=next[j]; } if(j>ls) return (i-ls); else return 0; } void String_Show(char *s) { while(putchar(*s++)); printf("\n"); } int main() { char *str,*c; int ans; c=(char *)malloc(sizeof(MAXSIZE)); printf("请输入主串:"); str=String_Create(); printf("请输入子串:"); gets(c); ans=String_IndexKMP(str,c,1); printf("子串在主串中的位置为:%d",ans); return 0; }

KMP算法 ，无法匹配不知道什么问题求看看

# include<stdio.h> # include<windows.h> int next_f(char*t, char*next); int f(char *s, char*t); int main(void) { char S[]{"asdasfafafa"}; char T[]{"fafa"}; f(S, T); system("pause"); return 0; } int next_f(char*t, char*next) { int i = -1; int j = 0; next[255]; next[0] = -1; while (j<strlen(t)) { if (i == -1 || t[i] == t[j]) { i++; j++; next[j] = i; } else{ i = next[i]; } } return 0; } int f(char *s, char*t) { int i = 0; int j = 0; char next[255]; next_f(t, next); while (i<strlen(s) && j<strlen(t)) { if (j == -1 || s[i] == t[j]) { i++; j++; } else { j = next[j]; } } if (j == strlen(t)) { printf("匹配成功\n"); } else{ printf("匹配不成功\n"); } return 0; }

#include "stdafx.h" #include "stdio.h" #define MaxSize 7 typedef struct //定义结构体类型 { char data[MaxSize]; int length; }SqString; void StrAssign(SqString &s,char cstr[]) //将一个字符串常量赋给串s { int i; for(i=0;cstr[i]!='\0';i++) s.data[i]=cstr[i]; s.length=i; } void GetNextval(SqString t,int nextval[]) //对模式串t求nextval[]值 { int j=0,k=-1; nextval[0]=-1; while(j<t.length) { if(k==-1||t.data[j]==t.data[k]) { j++;k++; if(t.data[j]!=t.data[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; } } int KMPIndex(SqString s,SqString t) { int nextval[MaxSize],i=0,j=0; GetNextval(t,nextval); while(i<s.length&&j<t.length) { if(j==-1||s.data[i]==t.data[j]) { i++; j++; } else j=nextval[j]; } if(j>=t.length) return(i-t.length); else return -1; } int main(int argc, char* argv[]) { SqString s1,s2; int k; char t[20]={'a','b','c','a','a','b','b','a','b','c','a','b','a','a','c','b','a','c','b','a'}; char p[7]={'a','b','c','a','b','a','a'}; StrAssign(s1,t); StrAssign(s2,p); k=KMPIndex(s1,s2); if(k!=-1) printf("匹配,从第%d个数开始",k); else printf("不匹配"); return 0; }

c语言kmp模式匹配如何处理文章，段落

KMP算法中的next函数值求法的原理

RT，是next函数值求法的[color=red]原理[/color]！不是求法！谢谢！ [code="java"]public int[] getNext(char[] pattern) { int pattern_len=pattern.length; int[] next=new int[pattern_len]; next[0]=-1;next[1]=0; for (int i = 2; i < pattern_len; i++) { int j=i; while(j>1) { if (pattern[i-1]==pattern[next[j-1]]) { next[i]=next[j-1]+1; break; }else { j=next[j-1]; } } if (j==1) { next[i]=1; } } return next; }[/code]

#include "stdafx.h" #include "stdio.h" #define MaxSize 21 typedef struct //定义结构体类型 { char data[MaxSize]; int length; }SqString; void StrAssign(SqString &s, char cstr[]) //将一个字符串常量赋给串s { int i; for (i = 0; cstr[i] != '\0'; i++) s.data[i] = cstr[i]; s.length = i; } void GetNextval(SqString t, int nextval[]) //对模式串t求nextval[]值 { int j = 0, k = -1; nextval[0] = -1; while (j<t.length) { if (k == -1 || t.data[j] == t.data[k]) { j++; k++; if (t.data[j] != t.data[k]) nextval[j] = k; else nextval[j] = nextval[k]; } else k = nextval[k]; } } int KMPIndex(SqString s, SqString t) { int nextval[MaxSize], i = 0, j = 0; GetNextval(t, nextval); while (i<s.length&&j<t.length) { if (j == -1 || s.data[i] == t.data[j]) { i++; j++; } else j = nextval[j]; } if (j >= t.length) return(i - t.length); else return -1; } int main(int argc, char* argv[]) { SqString s1, s2; int k; char t[21] = { 'a', 'b', 'c', 'a', 'a', 'b', 'b', 'a', 'b', 'c', 'a', 'b', 'a', 'a', 'c', 'b', 'a', 'c', 'b', 'a' }; char p[8] = { 'a', 'b', 'c', 'a', 'b', 'a', 'a' }; StrAssign(s1, t); StrAssign(s2, p); k = KMPIndex(s1, s2); if (k != -1) printf("匹配,从第%d个数开始", k); else printf("不匹配"); return 0;

String s = new String(" a ") 到底产生几个对象？

Linux面试题（2020最新版）

JVM内存结构和Java内存模型别再傻傻分不清了

JVM内存结构和Java内存模型都是面试的热点问题，名字看感觉都差不多，网上有些博客也都把这两个概念混着用，实际上他们之间差别还是挺大的。 通俗点说，JVM内存结构是与JVM的内部存储结构相关，而Java内存模型是与多线程编程相关，本文针对这两个总是被混用的概念展开讲解。 JVM内存结构 JVM构成 说到JVM内存结构，就不会只是说内存结构的5个分区，而是会延展到整个JVM相关的问题，所以先了解下

loonggg读完需要3分钟速读仅需 1 分钟大家好，我是你们的校长。我之前讲过，这年头，只要肯动脑，肯行动，程序员凭借自己的技术，赚钱的方式还是有很多种的。仅仅靠在公司出卖自己的劳动时...

85后蒋凡：28岁实现财务自由、34岁成为阿里万亿电商帝国双掌门，他的人生底层逻辑是什么？...

MySQL数据库面试题（2020最新版）

HashMap底层实现原理，红黑树，B+树，B树的结构原理 Spring的AOP和IOC是什么？它们常见的使用场景有哪些？Spring事务，事务的属性，传播行为，数据库隔离级别 Spring和SpringMVC，MyBatis以及SpringBoot的注解分别有哪些？SpringMVC的工作原理，SpringBoot框架的优点，MyBatis框架的优点 SpringCould组件有哪些，他们...