近似模式串匹配算法

A. 串的模式匹配是什么

就是拿T串从S串(称为主串)去寻找在S串是否存在这么一个T串,如果存在，则说明T串是S串的子串并返回首次查找成功的位置(也称为索引)。

它的算法原理是比较简单的，就是拿T串从S串的首位置(通常用一个变量来记住它的位置称为S串的指针)开始逐一匹配，如发生失配时则从S串的第二个位置开始重新匹配,依此类型，直到完全匹配为止,或指向S串的指针已到达末尾。 这种算法也称为朴素算法。效率是最低的。相应地效率高的是
由D.E.Knuth 美国计算机科学家人称算法之父高德纳和另两位科学家V.R.Pratt和J.H.Morris发明的KMP算法

B. C语言数据结构串的模式匹配算法问题

和while循环里面的一样，i指针退回原来的位置并指向下一位，应该是多少？i-j+2是吧！
这里不用指向下一位，直接return它的位置就行了，于是return
i-j+1
i-j+1和i-t[0]相等！

C. 实现串的简单模式匹配算法。要求：输入主串S和子串T，若在主串S中存在和T相等的子串，则返回在S中出现的

首先你得把主串和字串获取成两个字符数组，这部分我就不给你写了，假定我们已经有了两个数组s[]和t[]一下为匹配部分的算法：
int i,j,k;
for(i=0;i<t.lenth;t++ )
{
if(s[i]=t[0])
{
for(j=0;j<t.length;j++)
{
if(s[i+j]=t[j])
{
continue;
}
else
{
break;
}
}
if(j=(t.length-1))
{return i;}
continue;
}
continue;
}
return 0;

D. Java编程实现字符串的模式匹配

传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（n＊m），其中n和m分别为串s和串t的长度。

KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为Knuth－Morris－Pratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（n＋m）。

E. 字符串匹配的匹配种类

柔性字符串匹配
1974年Fischer和Paterson将通配符don't cares引入模式匹配问题 ，之后模式匹配的定义出现了各种各样非标准形式：按匹配方式分，有容错的近似匹配，交换相邻字母的交换匹配，服务于程序代码查错的参数匹配等；按匹配对象分，T、P可以是一张二维表，也可以分别含有通配符；按匹配结果分，有返回匹配位置和匹配数两种定义。Muthukrishna等人将上述各类问题统称为Non-standard Stringology 。然而，通配符的引入会让问题定义更加灵活，却也带来了复杂性。算法的设计有时不仅仅考虑时空效率，保证匹配结果的完备性很可能成为算法设计更重要的问题。甚至其中的某些问题被猜测具有NP难度。
带有通配符的串匹配
在Fischer和Paterson于1974年将通配符*引入模式匹配问题之后，如何将通配符与传统的模式匹配有效结合是研究的重点。这其中，最具代表性的定义是通配符指代的字符数不仅仅用一个固定的常数表示，而是一个可由用户自定义的区间 ，即带有上下限约束，如TCT*(30,50)TATA。 将上述带有区间的通配符扩展至任意两两相邻的字符之间，然而所有的通配符上下限相同，如A*(1,3)C*(1,3)G*(1,3)C。为了进一步放宽约束， 提出了不同通配符彼此独立的思想，如A*(0,3)C*(2,4)G*(1,1)C。 序列模式挖掘是数据挖掘的一个重要分支，是基于时间或者其他序列的经常发生的模式。序列模式的一个例子就是“一个9个月前买了一台PC的顾客有可能在一个月内买一个新的CPU”。很多数据都是这种时间序列形式的，我们就可以用它来市场趋势分析，客户保留和天气预测等等。序列模式首先是由R.Agrawal和R.Srikant提出的，随后几年研究者所提出的算法都是基于Apriori原理的改进算法。随后Zaki等人提出了基于垂直数据表示的SPADE算法。Han等提出了不产生候选集的基于模式增长的FP-Growth算法。接着Han等又研究出了基于投影数据库的FreeSpan和PrefixSpan算法。

F. 《数据结构（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 StrAssign(SString T,char * chars)//生成一个其值等于chars的串T
{
int i;
if (strlen(chars) > MAX_STR_LEN)
{
return ERROR;
}
else
{
T[0] = strlen(chars);
for (i=1; i<=T[0]; ++i)
{
T[i] = * (chars + i - 1);
}
return OK;
}
}
//返回串S的元素的个数
int StrLength(SString S)
{
return S[0];
}
//用Sub返回串S的自第pos个字符起长度为len的子串
Status SubString(SString Sub,SString S,int pos,int len)
{
int i;
if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
{
return ERROR;
}
for (i=1; i<=len; ++i)
{
Sub[i] = S[pos+i-1];
}
Sub[0] = len;
return OK;
}
//输出字符串T
void StrPrint(SString T)
{
int i;
for (i=1; i<=T[0]; ++i)
{
printf("%c ",T[i]);
}
printf("\n");
}
//求模式串T的next函数值并存入数组next
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
//求模式串T的next函数修正值并存入数组nextval
void get_nextval(SString T,int nextval[])
{
int i = 1,j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
if (T[i] != T[j])
{
nextval[i] = j;
}
else
{
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j];
}
}
}
//利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法
//1=<pos=<StrLength(S)
int Index_KMP(SString S,SString T,int pos,int next[])
{
int i = pos,j = 1;
while (i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
int main(void)
{
int i,* p;
SString s1,s2;
StrAssign(s1,"aaabaaaab");
printf("主串为：");
StrPrint(s1);
StrAssign(s2,"aaaab");
printf("子串为：");
StrPrint(s2);
p = (int *)malloc((StrLength(s2) + 1) * sizeof(int));
get_next(s2,p);
printf("子串的next的数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
i = Index_KMP(s1,s2,1,p);
if (i)
{
printf("主串和子串在第%d个字符处首次匹配\n",i);
}
else
{
printf("主串和子串匹配不成功\n");
}
get_nextval(s2,p);
printf("子串的nextval数组为：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
printf("主串和子串在第%d个字符处首次匹配\n",Index_KMP(s1,s2,1,p));
printf("求串s1的从第5个字符起长度为5的子串s2:\n");
SubString(s2,s1,5,5);
printf("串s2为:");
StrPrint(s2);
return 0;
}
/*
在vc++6.0中的输出结果：
------------------------
主串为：a a a b a a a a b
子串为：a a a a b
子串的next的数组为：0 1 2 3 4
主串和子串在第5个字符处首次匹配
子串的nextval数组为：0 0 0 0 4
主串和子串在第5个字符处首次匹配
求串s1的从第5个字符起长度为5的子串s2:
串s2为:a a a a b
Press any key to continue
------------------------------
*/

G. 数据结构串匹配十大经典算法

1。
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。

int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函数值求T在主串S中第pos 个字符之后的位置的KMP算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函数：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next

我现在只有这两个答案。

H. 数据结构（c++）字符串 模式匹配算法问题，对高手来说只要写一点点

#include <string>
using namespace std;

string s = "zabcdefg";

int index1(const string ss, int pos)
{
if (pos<0 || pos>s.length())
printf("pos²»ºÏ·¨£¡");
int i = pos, j = 0;

while (i < s.length() && j < ss.length()) {
if (s[i]==ss[j]) {
i++;
j++;
} else {
i=i-j+1;
j=0;
}
}

if (j>=ss.length())
return (i-j+1);
else
return -1;
}
void getnext(const string ss, int *next)
{
int i = 0, j = -1;
next[i] = -1;
while (i < ss.length()) {
if (j == -1 || s[i] == ss[j]) {
i++;
j++;
next[i]=j;
} else
j = next[j];
}
}

int index2(const string ss, int pos)
{
int *next = new int[ss.length()];
getnext(ss, next);

int i = pos, j = 0;
while (i < s.length() && j < ss.length()) {
if (j==0 || s[i]==ss[j] ) {
++i;
++j;
} else {
j = next[j];
}
}

if (j >= ss.length())
return i-ss.length()+1;
else
return -1;
}

int main()
{
string ss = "abc";
printf("index1: %d, index2: %d\n", index1(ss, 0), index2(ss, 0));

return 0;
}

I. 串模式匹配算法（C语言）100分悬赏

第一个朴素算法:
1.普通的串模式匹配算法:
int index(char s[],char t[],int pos)
/*查找并返回模式串T在S中从POS开始的位置下标,若T不是S的子串.则返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分别指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //计算主串和模式串的长度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}

第二个KMP算法.该算法支持从主串的任意位置开始搜索.
2.KMP算法:
//求模式串的next函数.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}

//KMP模式匹配算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函数,求P在主串S中从第POS个字符开始的位置*/
/*若匹配成功.则返回模式串在主串中的位置下标.否则返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];

J. 串的模式匹配

基本思想：从主串s的第pos个字符起和模式的地一个字符比较，若等，则继续，否则从主串的下个字符起再重新和模式字符比较，直到全部符合。
基本算法：int Index(SSteing T,int pos)
{i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{if(S[i]++T[j]){++i;++j;}
else{i=i-j+2;j=1;}
}
if(j>T[0])return i-T[0];
else return 0;
}