home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / GCC / GERLIB_DEV08B.LHA / gerlib / libg++ / etc / ADT-examples / kmp.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-12  |  11.0 KB  |  315 lines
  1. #ifdef amiga
  2. #include <use_standard_argc_argv.h>
  3. #endif
  4.  
  5. //From: "Douglas C. Schmidt" <schmidt@zola.ICS.UCI.EDU>
  6. //Date: Fri, 28 Jul 89 11:47:11 -0700
  7.  
  8. /* Nifty little program that illustrates an implementation of the Knuth, 
  9.    Morris, Pratt string matching algorithm.
  10.  
  11.    This program has a user interface similar to fgrep, i.e., when
  12.    you provide it with a fixed pattern it prints out all the lines
  13.    from the standard input (or one user-specified input file) that 
  14.    contain at least one substring that matches the provided pattern. 
  15.    
  16.    Relevant options are:
  17.    
  18.    -i: Ignore case when performing comparisons. 
  19.    -n: Print out lines numbers along with the matching lines.
  20.    -v: Print out lines that *don't* match the pattern.
  21.  
  22.    The code below is extensively commented.  If these comments
  23.    distract you, run the code through g++ -E first ;-). */
  24.    
  25. #include <stdio.h>
  26. #include <std.h>
  27. #include <GetOpt.h>
  28.  
  29. /* This array is designed for mapping upper and lower case letter
  30.    together for a case independent comparison.  The mappings are
  31.    based upon the ASCII character sequences. */
  32. char charmap[] = 
  33. {
  34.     '\000', '\001', '\002', '\003', '\004', '\005', '\006', '\007',
  35.     '\010', '\011', '\012', '\013', '\014', '\015', '\016', '\017',
  36.     '\020', '\021', '\022', '\023', '\024', '\025', '\026', '\027',
  37.     '\030', '\031', '\032', '\033', '\034', '\035', '\036', '\037',
  38.     '\040', '\041', '\042', '\043', '\044', '\045', '\046', '\047',
  39.     '\050', '\051', '\052', '\053', '\054', '\055', '\056', '\057',
  40.     '\060', '\061', '\062', '\063', '\064', '\065', '\066', '\067',
  41.     '\070', '\071', '\072', '\073', '\074', '\075', '\076', '\077',
  42.     '\100', '\141', '\142', '\143', '\144', '\145', '\146', '\147',
  43.     '\150', '\151', '\152', '\153', '\154', '\155', '\156', '\157',
  44.     '\160', '\161', '\162', '\163', '\164', '\165', '\166', '\167',
  45.     '\170', '\171', '\172', '\133', '\134', '\135', '\136', '\137',
  46.     '\140', '\141', '\142', '\143', '\144', '\145', '\146', '\147',
  47.     '\150', '\151', '\152', '\153', '\154', '\155', '\156', '\157',
  48.     '\160', '\161', '\162', '\163', '\164', '\165', '\166', '\167',
  49.     '\170', '\171', '\172', '\173', '\174', '\175', '\176', '\177',
  50.     '\200', '\201', '\202', '\203', '\204', '\205', '\206', '\207',
  51.     '\210', '\211', '\212', '\213', '\214', '\215', '\216', '\217',
  52.     '\220', '\221', '\222', '\223', '\224', '\225', '\226', '\227',
  53.     '\230', '\231', '\232', '\233', '\234', '\235', '\236', '\237',
  54.     '\240', '\241', '\242', '\243', '\244', '\245', '\246', '\247',
  55.     '\250', '\251', '\252', '\253', '\254', '\255', '\256', '\257',
  56.     '\260', '\261', '\262', '\263', '\264', '\265', '\266', '\267',
  57.     '\270', '\271', '\272', '\273', '\274', '\275', '\276', '\277',
  58.     '\300', '\341', '\342', '\343', '\344', '\345', '\346', '\347',
  59.     '\350', '\351', '\352', '\353', '\354', '\355', '\356', '\357',
  60.     '\360', '\361', '\362', '\363', '\364', '\365', '\366', '\367',
  61.     '\370', '\371', '\372', '\333', '\334', '\335', '\336', '\337',
  62.     '\340', '\341', '\342', '\343', '\344', '\345', '\346', '\347',
  63.     '\350', '\351', '\352', '\353', '\354', '\355', '\356', '\357',
  64.     '\360', '\361', '\362', '\363', '\364', '\365', '\366', '\367',
  65.     '\370', '\371', '\372', '\373', '\374', '\375', '\376', '\377',
  66. };
  67.  
  68. /* The list of available program options. */
  69. enum options
  70. {
  71.   DEBUG, FOLD_CASE, LINE_NUMBERS, INVERSE, OPTION_SIZE
  72. };
  73.  
  74. /* Vector storing the enabled options (all initially disabled). */
  75. char option[OPTION_SIZE];
  76.  
  77. /* Data and function members necessary to implement the KMP algorithm. */
  78. class kmp
  79. {
  80. private: 
  81.  
  82. #ifdef GNUG
  83.   const int RESET_PATTERN_FLAG = -1;
  84. #else
  85. #define RESET_PATTERN_FLAG -1
  86. #endif  
  87.  
  88.   int  *fail_trans_table; /* Stores the generated nfa used when matching. */
  89.   char *pattern;          /* Stores the user-supplied pattern. */
  90.   int   pattern_len;      /* Pattern length. */
  91.  
  92.   void print_fail_trans_table (void);
  93.  
  94. public:
  95.   kmp (char *pattern, int pattern_len, int debug = 0);
  96.  ~kmp () { delete fail_trans_table; }
  97.   int operator ()(char *text, int text_len);
  98. };
  99.  
  100. /* Provide a debugging dump of the failure function.  Nothing fancy... */
  101.  
  102. void
  103. kmp::print_fail_trans_table (void)
  104. {
  105.   int i;
  106.   
  107.   for (i = 0; i < pattern_len; i++)
  108.     printf ("%3d,", i);
  109.  
  110.   putchar ('\n');
  111.  
  112.   for (i = 0; i < pattern_len; i++)
  113.     printf ("%3d,", fail_trans_table [i]);
  114.  
  115.   putchar ('\n');
  116. }
  117.  
  118. /* This constructor builds the transition table that encodes the failure function 
  119.    automaton.  The table stores the PATTERN index we go to in the event of a 
  120.    mismatch with the input text string.  This generation process runs in time 
  121.    linear to the pattern size. 
  122.    
  123.    The terms SUFFIX and PREFIX used below are defined in terms of each other.  
  124.    That is, at each state of the failure function we seek to determine the largest 
  125.    pattern prefix that matches with the largest suffix in the actual input text.  
  126.    This information informs us how far we can legitimately shift the pattern to the 
  127.    right when a mismatch occurs during the string matching process. 
  128.    
  129.    Stated more formally, this means that for all i (0 <= i <= (PATTERN_LEN - 1))
  130.    FAIL_TRANS_TABLE (i) is the largest j < i, such that PATTERN[1..j - 1] 
  131.    is a suffix of PATTERN[1..i - 1] and PATTERN[i] != PATTERN[j]. */
  132.  
  133. kmp::kmp (char *pat, int len, int debug):
  134.   pattern (pat), fail_trans_table (new int[len]), pattern_len (len)
  135. {
  136.   /* Points 1 beyond the rightmost potential *suffix* in the pattern (which is 
  137.      actually simulating the behavior of an actual input text string. */
  138.   int suffix_end = 0;
  139.  
  140.   /* Points 1 beyond the rightmost potential *prefix* in the pattern. */
  141.   int prefix_end = fail_trans_table[suffix_end] = RESET_PATTERN_FLAG;
  142.   
  143.   do
  144.     {
  145.       /* This WHILE loop uses the precomputed failure function to look further 
  146.          left into the pattern trying to find an index location where the pattern 
  147.          prefix matches the pattern suffix.  However, if/when we locate the
  148.          RESET_PATTERN_FLAG this means that we can just skip ahead to the next 
  149.          character in the input text. */
  150.          
  151.       while (prefix_end != RESET_PATTERN_FLAG 
  152.              && pattern[suffix_end] != pattern[prefix_end])
  153.         prefix_end = fail_trans_table[prefix_end];
  154.  
  155.       /* Once SUFFIX_END and PREFIX_END are pre-incremented below we know that 
  156.          the first PREFIX_END characters of PATTERN match the characters in 
  157.          positions PATTERN[SUFFIX_END - PREFIX_END .. SUFFIX_END - 1], i.e.,
  158.          the last PREFIX_END characters in the rightmost part of the first 
  159.          SUFFIX_END - 1 characters in PATTERN.
  160.         
  161.          If the character at location PATTERN[SUFFIX_END] matches that at 
  162.          PATTERN[PREFIX_END] it is silly to have the failure transition
  163.          jump to that pattern location (since it would immediately fail to
  164.          match, of course!). Instead, in that case we just ``borrow'' the
  165.          previously computed transition stored at FAIL_TRANS_TABLE[PREFIX_END]
  166.          and use it. */
  167.  
  168.       if (pattern[++suffix_end] == pattern[++prefix_end])
  169.         fail_trans_table[suffix_end] = fail_trans_table[prefix_end];
  170.       else
  171.         fail_trans_table[suffix_end] = prefix_end;
  172.     }
  173.   /* Adding the extra 1 here is necessary since C strings are
  174.      indexed from 0 to pattern_len - 1... */
  175.  
  176.   while (suffix_end + 1 < pattern_len);
  177.  
  178.   if (debug)
  179.     print_fail_trans_table ();
  180. }
  181.  
  182. /* Actually perform the KMP matching algorithm using the generated determinisitic 
  183.    pattern matching match encoded in the failure transition table.  This version 
  184.    is optimized on the assumption that there will be more characters in the text 
  185.    input that *don't* match the pattern than ones that do match it. Therefore, we 
  186.    make a special effort to keep looping through the failure function as long as 
  187.    the text and pattern don't match. */
  188.  
  189. int
  190. kmp::operator ()(char *text, int text_len)
  191. {
  192.   int suffix_end = RESET_PATTERN_FLAG;
  193.   int prefix_end = RESET_PATTERN_FLAG;
  194.  
  195.   /* If TEXT length is shorted than PATTERN we'll bail out now... */
  196.   if (text_len < pattern_len)
  197.     return 0;
  198.     
  199.   /* Split the following two cases so that we don't pay any
  200.      unnecessary overhead when case folding is not required. */
  201.   if (option[FOLD_CASE])
  202.   
  203.   /* Note how this main loop is almost identical with the 
  204.      `failure transition table building' algorithm used above. */
  205.  
  206.     do
  207.       {
  208.         /* Ignore case when matching and keep applying the failure function
  209.            until we get a match or are forced to restart the pattern (starting
  210.            with the *following* input text character, that is). */
  211.  
  212.         while (prefix_end != RESET_PATTERN_FLAG 
  213.                && charmap[text[suffix_end]] != charmap[pattern[prefix_end]])
  214.           prefix_end = fail_trans_table[prefix_end];
  215.  
  216.         if (prefix_end + 1 >= pattern_len)
  217.           return 1;
  218.         else
  219.           ++suffix_end, ++prefix_end;
  220.       }
  221.  
  222.     /* This conditional expression is used to terminate the search when it
  223.        becomes clear that we can't match the PATTERN since the TEXT has
  224.        fewer unexamined characters than the PATTERN length. */
  225.     while (text_len - suffix_end >= pattern_len - prefix_end);
  226.  
  227.   else
  228.  
  229.     /* This loop is identical with the preceding one, except that we don't
  230.        bother to fold case... */
  231.  
  232.     do
  233.       {
  234.         while (prefix_end != RESET_PATTERN_FLAG 
  235.                && text[suffix_end] != pattern[prefix_end])
  236.           prefix_end = fail_trans_table[prefix_end];
  237.  
  238.         if (prefix_end + 1 >= pattern_len)
  239.           return 1;
  240.         else
  241.           ++suffix_end, ++prefix_end;
  242.       }
  243.     while (text_len - suffix_end >= pattern_len - prefix_end);
  244.  
  245.   return 0;
  246. }
  247.  
  248. /* The name sez it all! */
  249.  
  250. void
  251. print_usage_and_die (char *prog_name)
  252. {
  253.   fprintf (stderr, "usage: %s [-inv] pattern [file]\n", prog_name);
  254.   exit (1);
  255. }
  256.  
  257. /* Main driver program.  Emulates certain useful features of fgrep. */
  258.    
  259. int
  260. main (int argc, char **argv)
  261. {
  262.   GetOpt getopt(argc, argv, "dinv");
  263.  
  264.   if (argc == 1)
  265.     print_usage_and_die (argv[0]);
  266.  
  267.   /* A rather arbitrary limit... */
  268.   const int MAX_LINE = 200;
  269.   char  text[MAX_LINE];
  270.   int   c;
  271.       
  272.   /* Initialize any user-specified options. */
  273.  
  274.   while ((c = getopt ()) != EOF)
  275.     switch (c)
  276.       {
  277.       case 'd': option[DEBUG] = 1; break;
  278.       case 'i': option[FOLD_CASE] = 1; break;
  279.       case 'n': option[LINE_NUMBERS] = 1; break;
  280.       case 'v': option[INVERSE] = 1; break;
  281.       default:  print_usage_and_die (argv[0]);
  282.       }
  283.       
  284.   /* Call the constructor to build the failure function table. */
  285.   kmp match (argv[getopt.optind], strlen (argv[getopt.optind]), option[DEBUG]);
  286.  
  287.   /* Handle a user-specified input file. */
  288.   if (argv[++getopt.optind] && !freopen (argv[getopt.optind], "r", stdin))
  289.     {
  290.       perror (argv[0]); return 1;
  291.     }
  292.   
  293.   /* Split the following into two separate cases to avoid overhead 
  294.      when line numbers are not required. */
  295.   if (option[LINE_NUMBERS])
  296.     {
  297.       int line;
  298.       
  299.       for (line = 1; gets (text); line++)
  300.         if (match (text, strlen (text)) != option[INVERSE])
  301.           printf ("%d:%s\n", line, text);
  302.  
  303.     }
  304.   else
  305.     {
  306.  
  307.       while (gets (text))
  308.         if (match (text, strlen (text)) != option[INVERSE])
  309.           puts (text);
  310.  
  311.     }
  312.   return 0;
  313. }
  314.  
  315.