posts - 33,  comments - 33,  trackbacks - 0
这两题是单模式串匹配
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 *= 0;
20        char *= 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 阅读(1217) 评论(0)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理