這兩題是單模式串匹配
hdu2087 數據量較小，可以采用標準庫strstr輕松完成
1
#include <stdio.h>
2#include <string.h>
3
4char pat[1024];
5char buf[1024];
6
7
8int main()
9
{
10
//freopen("data.txt","r",stdin);
11 while(scanf("%s",buf) != EOF)
12
{
13 if (buf[0] == '#')
14 {
15 break;
16
}
17 scanf("%s",pat);
18 int len = strlen(pat);
19 char *p = 0;
20 char *k = buf;
21 int cnt = 0;
22 while((p = strstr(k,pat)) != 0)
23 {
24 ++cnt;
25 k = p+len;
26 }
27 printf("%d\n",cnt);
28 }
29 return 0;
3 0
} hdu 1686
這里使用kmp的思想，使得指向被匹配的串指針無需回溯
1
#include <iostream>
2#include <string>
3using namespace std;
4
5int next[10005];
6
7//已知next[j] = k
8//設next[j+1] = k’
9//P[0,1,2….k’] = P[j-k’,j-k’+1,….j+1]
10
11
12void compNext(const string& _pattern)
13
{
14
int len = _pattern.length();
15 int p1 = -1;
16 int p2 = 0;
17 for (int i = 0; i < len; ++i)
18
{
19 next[i] = -1;
20
}
21 while(p2 < len )
22 {
23 while(p1 != -1 && _pattern[p1] != _pattern[p2])
24 p1 = next[p1];
25 ++p1;++p2;
26 if (_pattern[p1] == _pattern[p2])
27 {
28 next[p2] = next[p1];
29 }
30 else
31 {
32 next[p2] = p1;
33 }
34 }
35
}
36
37
38int kmp(const char* _str,int _lenS,const string& _pattern)
39{
40 int len = _pattern.length();
41 int pp = 0;
42 int ps = 0;
43 int cnt= 0;
44 while((ps < _lenS) )
45 {
46 if (_str[ps] == _pattern[pp])
47 {
48 ++pp;
49 ++ps;
50 }
51 else
52 {
53 if (next[pp] != -1)
54 {
55 pp = next[pp];
56 }
57 else
58 {
59 pp = 0;
60 ++ps;
61 }
62 }
63 if (pp >= len)
64 {
65 ++cnt;
66 if (next[pp] != -1)
67 {
68 pp = next[pp];
69 }
70 else
71 {
72 pp = 0;
73 ++ps;
74 }
75 }
76 }
77
78 return cnt;
79}
80
81string pattern;
82string str;
83void Test()
84{
85 cin >> pattern >> str;
86 compNext(pattern);
87 int cnt = kmp(str.c_str(),str.length(),pattern);
88 printf("%d\n",cnt);
89}
90
91int main()
92{
93 freopen("data.txt","r",stdin);
94 int tc;
95 cin >> tc;
96 for (int i = 0; i < tc; ++i)
97 {
98 Test();
99 }
100 return 0;
101} posted on 2012-03-29 20:13
bennycen 閱讀(1269)
評論(0) 編輯 收藏 引用 所屬分類:
算法題解