一,题目
给一串很长字符串,要求找到符合要求的字符串,例如目的串:123
例如:1******3***2 ,12*****3这些都要找出来
生活中,比如输入:法你轮和功 会被和谐的
二,分析:
自然匹配就是对待匹配的每个字符挨个匹配,设你的待匹配字串长度位n,模式字符串长度位m。对于待匹配字符串中的任意一个字符最坏情况下要匹配m次,也就是说这个字符不在模式字符串中。所以最坏情况下总共是m*n此匹配,时间复杂度就是O(m*n)
倘若使用hash表对待字符串进行hash处理O(n)的时间复杂度,那么对于模式字符串中的任意字符,仅需一次hash判断就可以得知是否在待匹配字符串中出现。最坏仅需m次就可以得到结果。时间复杂度为O(m)或者O(n);
与此题相类似:就是给一个很长的字符串str还有一个字符集比如{a,b,c}找出str里包含{a,b,c}的最短子串。要求O(n)?比如,字符集是a,b,c,字符串是abdcaabcx,则最短子串为abc。
用两个变量front rear指向一个的子串区间的头和尾,用一个int
cnt[255]={0}记录当前这个子串里字符集a,b,c各自的个数,一个变量sum记录字符集里有多少个了rear一直加,更新cnt[]和sum的值,直到
sum等于字符集个数然后front++,直到cnt[]里某个字符个数为0,这样就找到一个符合条件的字串了继续前面的操作,就可以找到最短的了。
鉴于此题的解答,我给出的答案是,利用哈希表(散列表)即根据关键码值(Key value)而直接进行访问的数据结构。下面源码是给出的基于ASCII码表的和谐过程。如果是汉字的,将会更复杂些。这里没有给出。不过,思路类似。
三,源码
#include <iostream>
using namespace std;
//强大的和谐系统
int main()
{
char *src="anbmcj";
char *des="abc";
//创建一个哈希表,并初始化
const int tableSize = 256; //因为ASCII码共有256个
int hashTable[tableSize];
int len,i;
for(i = 0; i < tableSize; i++)
hashTable[i] = 0;
len = strlen(src);
for(i = 0; i < len; i++)
hashTable[src[i]] = 1;
len = strlen(des);
for(i = 0; i < len; i++)
{
if(hashTable[des[i]] == 0)//如果des中的任何一个字母没有,则匹配失败
{
cout<<"和谐失败,为正规内容"<<endl;
}
}
cout<<"您的内容被和谐"<<endl;
return 1; //匹配成功
}
附表:
ASCII值
|
控制字符
|
ASCII值
|
控制字符
|
ASCII值
|
控制字符
|
ASCII值
|
控制字符
|
0
|
NUT
|
32
|
(space)
|
64
|
@
|
96
|
、
|
1
|
SOH
|
33
|
!
|
65
|
A
|
97
|
a
|
2
|
STX
|
34
|
”
|
66
|
B
|
98
|
b
|
3
|
ETX
|
35
|
#
|
67
|
C
|
99
|
c
|
4
|
EOT
|
36
|
$
|
68
|
D
|
100
|
d
|
5
|
ENQ
|
37
|
%
|
69
|
E
|
101
|
e
|
6
|
ACK
|
38
|
&
|
70
|
F
|
102
|
f
|
7
|
BEL
|
39
|
,
|
71
|
G
|
103
|
g
|
8
|
BS
|
40
|
(
|
72
|
H
|
104
|
h
|
9
|
HT
|
41
|
)
|
73
|
I
|
105
|
i
|
10
|
LF
|
42
|
*
|
74
|
J
|
106
|
j
|
11
|
VT
|
43
|
+
|
75
|
K
|
107
|
k
|
12
|
FF
|
44
|
,
|
76
|
L
|
108
|
l
|
13
|
CR
|
45
|
-
|
77
|
M
|
109
|
m
|
14
|
SO
|
46
|
.
|
78
|
N
|
110
|
n
|
15
|
SI
|
47
|
/
|
79
|
O
|
111
|
o
|
16
|
DLE
|
48
|
0
|
80
|
P
|
112
|
p
|
17
|
DCI
|
49
|
1
|
81
|
Q
|
113
|
q
|
18
|
DC2
|
50
|
2
|
82
|
R
|
114
|
r
|
19
|
DC3
|
51
|
3
|
83
|
X
|
115
|
s
|
20
|
DC4
|
52
|
4
|
84
|
T
|
116
|
t
|
21
|
NAK
|
53
|
5
|
85
|
U
|
117
|
u
|
22
|
SYN
|
54
|
6
|
86
|
V
|
118
|
v
|
23
|
TB
|
55
|
7
|
87
|
W
|
119
|
w
|
24
|
CAN
|
56
|
8
|
88
|
X
|
120
|
x
|
25
|
EM
|
57
|
9
|
89
|
Y
|
121
|
y
|
26
|
SUB
|
58
|
:
|
90
|
Z
|
122
|
z
|
27
|
ESC
|
59
|
;
|
91
|
[
|
123
|
{
|
28
|
FS
|
60
|
<
|
92
|
/
|
124
|
|
|
29
|
GS
|
61
|
=
|
93
|
]
|
125
|
}
|
30
|
RS
|
62
|
>
|
94
|
^
|
126
|
~
|
31
|
US
|
63
|
?
|
95
|
—
|
127
|
DEL
|
NUL 空
|
VT 垂直制表
|
SYN 空转同步
|
SOH 标题开始
|
FF 走纸控制
|
ETB 信息组传送结束
|
STX 正文开始
|
CR 回车
|
CAN 作废
|
ETX 正文结束
|
SO 移位输出
|
EM 纸尽
|
EOY 传输结束
|
SI 移位输入
|
SUB 换置
|
ENQ 询问字符
|
DLE 空格
|
ESC 换码
|
ACK 承认
|
DC1 设备控制1
|
FS 文字分隔符
|
BEL 报警
|
DC2 设备控制2
|
GS 组分隔符
|
BS 退一格
|
DC3 设备控制3
|
RS 记录分隔符
|
HT 横向列表
|
DC4 设备控制4
|
US 单元分隔符
|
LF 换行
|
NAK 否定
|
DEL 删除
|
分享到:
相关推荐
已知一任意长度字符串str,以00h结束,长度小于200h,编写汇编程序实现在该字符串中搜索匹配子串substr(以00h结束,长度小于80)。 若找到,则将found单元置为ffh,并将匹配位置(以字符串str首地址为0参考点)存放在...
中文匹配C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 C#中文文本匹配,字符串匹配,中文词语匹配,计算多个句子相似度 C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 C#中文文本...
带通配符的字符串匹配算法,带通配符的字符串匹配算法
典型的字符串模式匹配算法,ACM比赛里面的常客,处理恶心模拟题的好帮手
字符匹配 后缀自动机
字符串匹配 用汇编语言编写“在字符串中查找输入字符 ”,也就是字符串匹配
运用C++实现中文字符的KMP匹配算法,实现关键字搜索
华为od 华为od_华为od练习题之求字符串字符匹配_题库题解
其中,第一个字符串为模式。其余为待测字符串。 【输出形式】 将匹配于模式的字符串输出到标准输出,每行一个。 【输入样例】 abcd?123* abce123 abcda12345 abcda123 1234 【输出样例】 ...
本程序用CUDA编程在linux环境下实现并行的进行字符串匹配的操作。
python实现字符串模糊匹配
isMobileSimple : 验证手机号(简单) isMobileExact : 验证手机号(精确) isTel : 验证电话号码 isIDCard15 : 验证身份证号码15...getReplaceFirst: 替换正则匹配的第一部分 getReplaceAll : 替换所有正则匹配的部分
C++实现字符串匹配函数,匹配中可以包括通配符
实验二,微机软件实验2-字符匹配实验.rar,,微机原理实验,附代码和一些参考图
C++的字符串匹配的应用文档。有代码和详细注释。主要取自王红梅的C++数据结构。加上自己的整理。
先对两个字符串进行比较,然后对字符进行匹配,假如相同,则返回一个字符串从第一个字符相同是的位置
一个可以利用指定字符串对目标文本进行匹配的c程序
相似字符串匹配过滤算法研究.
OC的字符串匹配库.包含KMP匹配 ,AC 多模字符串匹配.
微机原理实验四字符匹配程.doc