珞珈山水BBS -- 单文区文章阅读

搜索

单文区文章阅读 [返回]
发信人: niba (泥巴), 信区: Programm 标题: Re: 有谁知道在文件里查找给定字符串编程的思路？发信站: BBS 珞珈山水站 (Sat Apr 23 23:09:31 2005) 【在 foxfat (keven.r) 的大作中提到: 】 : rt，谢谢了！~~ 很多算法的。比如KMP,BM,BMH等等。当然这些算法都是在数据量比较大的时候才有优势。一般就用strs tr就可以了。给你一段BMH的程序吧(不是我写的，但可以用)。 #include <string.h> #include <assert.h> #include <stdio.h> class Search { static const int MAXCHAR = 256; int d[MAXCHAR]; int m; char* patt; public: Search(char); int find(char); }; Search::Search(char* p) { assert(p); patt = p; m = strlen(patt); int k = 0; for (k = 0; k < MAXCHAR; k++) d[k] = m; for (k = 0; k < m - 1; k++) d[patt[k]] = m - k - 1; } int Search::find(char* text) { assert(text); int n = strlen(text); if (m > n) return -1; int k = m - 1; while (k < n) { int j = m - 1; int i = k; while (j >= 0 && text[i] == patt[j]) { j--; i--; } if (j == -1) return i + 1; k += d[text[k]]; } return -1; } #ifdef DRIVER int main(int argc, char* argv[]) { assert(argc == 3); const int MAXLINE = 256; char fbuf[MAXLINE]; Search patt(argv[1]); FILE* fp = fopen(argv[2], "r"); assert(fp); int nf = 0; while (fgets(fbuf, MAXLINE, fp) != NULL) { if (patt.find(fbuf) != -1) { fputs(fbuf, stdout); nf++; } } fclose(fp); return !nf; } #endif -- ※ 来源:·珞珈山水BBS站 http://bbs.whu.edu.cn·[FROM: 211.161.150.*]
[返回单文区目录]

单文区文章阅读 [返回]

发信人: niba (泥巴), 信区: Programm
标  题: Re: 有谁知道在文件里查找给定字符串编程的思路？
发信站: BBS 珞珈山水站 (Sat Apr 23 23:09:31 2005)

【在 foxfat (keven.r) 的大作中提到: 】
: rt，谢谢了！~~

很多算法的。
比如KMP,BM,BMH等等。当然这些算法都是在数据量比较大的时候才有优势。一般就用strs
tr就可以了。给你一段BMH的程序吧(不是我写的，但可以用)。
#include <string.h>
        #include <assert.h>
        #include <stdio.h>

        class Search {
                static const int MAXCHAR = 256;
                int d[MAXCHAR];
                int m;
                char* patt;
        public:
                Search(char*);
                int find(char*);
        };

        Search::Search(char* p)
        {
                assert(p);

                patt = p;
                m = strlen(patt);

                int k = 0;

                for (k = 0; k < MAXCHAR; k++)
                        d[k] = m;

                for (k = 0; k < m - 1; k++)
                        d[patt[k]] = m - k - 1;
        }

        int Search::find(char* text)
        {
                assert(text);

                int n = strlen(text);
                if (m > n)
                        return -1;

                int k = m - 1;

                while (k < n) {
                        int j = m - 1;
                        int i = k;
                        while (j >= 0 && text[i] == patt[j]) {
                                j--;
                                i--;
                        }
                        if (j == -1)
                                return i + 1;
                        k += d[text[k]];
                }

                return -1;
        }

        #ifdef DRIVER
        int main(int argc, char* argv[])
        {
                assert(argc == 3);

                const int MAXLINE = 256;
                char fbuf[MAXLINE];
                Search patt(argv[1]);
                FILE* fp = fopen(argv[2], "r");
                assert(fp);
                int nf = 0;

                while (fgets(fbuf, MAXLINE, fp) != NULL) {
                        if (patt.find(fbuf) != -1) {
                                fputs(fbuf, stdout);
                                nf++;
                        }
                }

                fclose(fp);

                return !nf;
        }
        #endif

--

※ 来源:·珞珈山水BBS站

http://bbs.whu.edu.cn·[FROM: 211.161.150.*]

[返回单文区目录]