rambo

字符串匹配（一）

2015年8月10日 Data Strcuture 0 Comments

字符串匹配问题

假定文本是一个长度为n的数组T[1,...,n]，而模式是一个长度为m的数组P[1,...,m]，其中m\leq n，进一步假设P和T的元素都是来自一个有限字母集\sum的字符。

QQ截图20150810200731

QQ截图20150810200703

朴素算法

1
2
3
4
5
6
NAIVE-STRING-MATCHER(T,P)
1  n=T.length;
2  m=P.length
3  for  s=0 to n-m (闭区间)
4          if P[0,...,m-1]==T[s+1,...,s+m-1]   // strcmp(const char *str1, const char *str2)
5             return "Matching"

时间复杂度分析

在最坏情况下，朴素字符串匹配算法运行时间为O(n-m+1)m)。例如，在考察文本字符串a^{n}（一串由n个a组成的字符串）和模式a^{m}时，对偏移s的n-m+1个可能值中的每一个，在第四行比较相应字符的隐式循环必须执行m次来确定偏移的有效性。因此，最坏情况下的运行时间是\Theta((n-m+1)m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstring>
#include <string>
#include <cstdlib>
using namespace std;
 
 
int strcmp(const char *str1, const char *str2){
/*不可用while(*str1++==*str2++)来比较，当不相等时仍会执行一次++，
return返回的比较值实际上是下一个字符。应将++放到循环体中进行。*/
while (*str1 == *str2){
if (*str1 == '\0')
return 0;
str1++;
str2++;
}
return *str1 - *str2;
}
 
//截取字符串某个特定区间
char *substring(const char str[], int s,int m) {
char *strT = (char *)malloc(sizeof(char) * (m + 1));
for (int i = 0; i < m; i++){
strT[i] = str[s + i];
}
strT[m] = '\0';
return strT;
}
 
//extern int strcmp(const char *s1,const char *s2);
int NAIVE_STRING_MATCHER(string T, string P){
int n = T.length();
int m = P.length();
int result = 0;
const char *comparestr = P.c_str();
        const char *totalstr = T.c_str();
for (int s = 0; s <= n - m; s++){
const char *substr = substring(totalstr, s, m);
result = strcmp(comparestr, substr);
}
 
return result;
}
 
int _tmain(int argc, _TCHAR* argv[]){
string T = "acaabc";
string P = "aab";
int result = NAIVE_STRING_MATCHER(T, P);
return 0;
}

相关问题：
1）假设模式P中的所有字符都不同，试说明如何对一段n个字符的文本T加速过程的执行速度，让朴素字符串匹配的速度达到O(n)呢？（和m没有关系咯）

答：当比较过程进行到P[j+1]和T[i+1]时，必有P[1,...,j]=T[i-j+1,...,i]。因为模式P中的所有字符都不相同，所以T[i-j+1,...,i]中的字符也均不同。也就是说，对于T[i-j+2,...,i]中的每个字符c，c!=T[i-j+1]=P[1]。

若T[i+1]！=P[j+1]，下一步比较只需从T[i+1]和P[1]开始比较，而不是从T[i-j+2]和P[1]开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int NAIVE_STRING_MATCHER1(string T, string P){
int n = T.length();
int m = P.length();
int result = 0;
const char *pattern= P.c_str();
const char *str = T.c_str();
int j = 0;
for (int s = 0; s <= n - m; s++){
if (str[s] == pattern[j]){
if (++j == m){
cout << "pattern occurs with shift s=" << s+1-m<<"~"<<s << endl;;
return 1;
}
}
else{
j = 0;
}
}
 
return false;
}
 
int _tmain(int argc, _TCHAR* argv[]){
string T = "abcfeabcdadfdf";
string P = "abcd";
int result = NAIVE_STRING_MATCHER1(T, P);
return 0;
}

QQ截图20150810210758

2）（很好的题目）假设允许模式P中包含一个间隔字符#，该字符可以和任意字符串匹配（甚至可以与长度为0的字符串匹配）。注意，间隔字符可以在模式中出现任意次，但假定它不会出现在文本中，试给出一种多项式运行时间的算法，以确定这样的模式P是否出现于给定的文本T中。

QQ截图20150810211916

 

答：设模式P中有k-1个# (k>1)，以#为分隔符把P分为k个部分，P1，P2，Pk，然后在文本T中使用NAIVE算法查找这k个部分。查找到Pi时，就从查找所在位置的后一位开始查找Pi+1）。

时间复杂度为（ 假设k个部分的长度为a1,a2,...,ak)。

O(n-a1+1)a1)+O((n-a1-a2)a2)+...+O((n-m-k+1)ak)
<O(n+1)a1)+O((n+1)a2)+...+O((n+1)ak)
<O(n+1)m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include "iostream"
using namespace std;
 
int strcmp(const char *str1, const char *str2){
/*不可用while(*str1++==*str2++)来比较，当不相等时仍会执行一次++，
return返回的比较值实际上是下一个字符。应将++放到循环体中进行。*/
while (*str1 == *str2){
if (*str1 == '\0')
return 0;
 
str1++;
str2++;
}
return *str1 - *str2;
}
 
void  mystrfind(const char*str, const char cmp,vector<int>& a){
int num = 0;
while (*str != '\0'){
num++;
str++;
if (*str == cmp){
a.push_back(num);
num = -1;//减1，去掉算上“#”
}
}
a.push_back(num);
}
 
int NAIVE_STRING_MATCHER3(string T, string P,const char cmp){
const char *str = P.c_str();
vector<int> a;
mystrfind(str, cmp, a);
 
int pos = 0;
int pos2 = 0;
int result = 0;
const char *comparestr = P.c_str();
const char *totalstr = T.c_str();
 
int n = T.length();
int m = P.length();
bool Flag = false;
for (int i = 0; i < a.size(); i++){
Flag = false;
for (int s = pos; s <=n - a[i]; s++){
const char *substr = substring(totalstr, s, a[i]);
const char *pattern = substring(comparestr, pos2, a[i]);//加'\0'
if (strcmp(substr, pattern) == 0){
Flag = true;
pos = a[i] + 1+s;
pos2 += a[i] + 1;
break;
}
}
}
 
if (Flag == true){
cout << "Pattern Occurs" << endl;
}
else{
cout << "Pattern Not Occurs" << endl;
}
return Flag;
}
 
int main( ){
string T = "cabccbacbacab";
string P = "ab#ba#c";
const char cmp = '#';
int result = NAIVE_STRING_MATCHER3(T,P,cmp);
cout << result << endl;
 
system("pause");
 
return 0;
}