# 算法题-字符串匹配算法

1. 传统的字符串匹配算法

```void NativeStrMatching( ElemType Target[], ElemType Pattern[] )
{
register int TarLen = 0; // Length of Target
register int PatLen = 0; // Length of Pattern
// Compute the length of Pattern
while( '\0' != Pattern[PatLen] )
PatLen++;
while( '\0' != Target[TarLen] )
{
int TmpTarLen = TarLen;
for(int i=0; i<PatLen; i++)
{
if( Target[TmpTarLen++] != Pattern[i] )
break;
if( i == PatLen-1 )
cout<<"Native String Matching,pattern occurs with shift "<<TarLen<<endl;
}
TarLen++;
}
}```

C++代码:

```void NativeStrMatch(const string& target,const string& pattern){
int n=target.size();
int m=pattern.size();
for(int i=0;i<n;i++){
int k=i;
int j;
for(j=0;j<m&&target[k]==pattern[j];k++,j++)
;
if(j==m){
cout<<"Native string Matching occurs at "<<i<<endl;
}
}
}```

2. KMP算法

KMP算法就能很好地解决这个冗余问题。

KMP算法主要包括计算前缀数组以及利用这个前缀数组进行判断.

```// Compute Prefix function
void CptPfFunc( ElemType Pattern[], int PrefixFunc[] )
{
register int iLen = 0; // Length of Pattern[]
while( '\0' != Pattern[iLen] )
iLen++;
int LOLP = 0; // Lenth of longest prefix
PrefixFunc[1] = 0;
for( int NOCM=2; NOCM<iLen+1; NOCM++ ) // NOCM represent the number of characters matched
{
while( LOLP>0 && (Pattern[LOLP] != Pattern[NOCM-1]) )
LOLP = PrefixFunc[LOLP];
if( Pattern[LOLP] == Pattern[NOCM-1] )
LOLP++;
PrefixFunc[NOCM] = LOLP;
}
}```

```void KMPstrMatching( ElemType Target[], ElemType Pattern[] )
{
int PrefixFunc[MAX_SIZE];
register int TarLen = 0;
register int PatLen = 0;
// Compute the length of array Target and Pattern
while( '\0' != Target[TarLen] )
TarLen++;
while( '\0' != Pattern[PatLen] )
PatLen++;
// Compute the prefix function of Pattern
CptPfFunc( Pattern, PrefixFunc );
int NOCM = 0; // Number of characters matched
for( int i=0; i<TarLen; i++ )
{
while( NOCM>0 && Pattern[NOCM] != Target[i] )
NOCM = PrefixFunc[NOCM];
if( Pattern[NOCM] == Target[i] )
NOCM++;
if( NOCM == PatLen )
{
cout<<"KMP String Matching,pattern occurs with shift "<<i - PatLen + 1<<endl;
NOCM = PrefixFunc[NOCM];
}
}
}```

```#include <iostream>
#include <string>
using namespace std;
//compute prefix function
void CptPfFunc(const string& pattern,int* prefix){
size_t m=pattern.size();
int j=0;//length of longest prefix
prefix[1]=0;
for(int i=2;i<=m;i++){
while(j>0&&pattern[j]!=pattern[i-1])
j=prefix[j];
if(pattern[j]==pattern[i-1])
j++;
prefix[i]=j;
}
}
void KMPstrMatch(const string& target,const string& pattern){
int n=target.size();
int m=pattern.size();
int *prefix=new int[m+1];
CptPfFunc(pattern,prefix);
int j=0;
for(int i=0;i<n;i++){
while(j>0&&pattern[j]!=target[i])
j=prefix[j];
if(pattern[j]==target[i])
j++;
if(j==m){
cout<<"KMP string Matching occurs at "<<i-j+1<<endl;
j=prefix[j];
}
}
delete [] prefix;
}```

http://billhoo.blog.51cto.com/2337751/411486

http://www.matrix67.com/blog/archives/115/

11.Algorithm Gossip: 字符串核对

 其它 J U S T 4 3 2 1 4（match?）

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void table(char*); // 建立前进表
int search(int, char*, char*); // 搜寻关键字
void substring(char*, char*, int, int); // 取出子字符串
int skip[256];
int main(void) {
char str_input[80];
char str_key[80];
char tmp[80] = {'\0'};
int m, n, p;
printf("请输入字符串：");
gets(str_input);
printf("请输入搜寻关键字：");
gets(str_key);
m = strlen(str_input); // 计算字符串长度
n = strlen(str_key);
table(str_key);
p = search(n-1, str_input, str_key);
while(p != -1) {
substring(str_input, tmp, p, m);
printf("%s\n", tmp);
p = search(p+n+1, str_input, str_key);
}
printf("\n");
return 0;
}
void table(char *key) {
int k, n;
n = strlen(key);
for(k = 0; k <= 255; k++)
skip[k] = n;
for(k = 0; k < n - 1; k++)
skip[key[k]] = n - k - 1;
}
int search(int p, char* input, char* key) {
int i, m, n;
char tmp[80] = {'\0'};
m = strlen(input);
n = strlen(key);
while(p < m) {
substring(input, tmp, p-n+1, p);
if(!strcmp(tmp, key)) // 比较两字符串是否相同
return p-n+1;
p += skip[input[p]];
}
return -1;
}
void substring(char *text, char* tmp, int s, int e) {
int i, j;
for(i = s, j = 0; i <= e; i++, j++)
mp[j] = text[i];
tmp[j] = '\0';
}```
原文作者：Mr.Rico
原文地址: https://www.cnblogs.com/xkfz007/archive/2012/11/13/2767405.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。