home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / NOTEPAD2.ZIP / NPKMP.C < prev    next >
C/C++ Source or Header  |  1989-02-08  |  2KB  |  72 lines
  1. /***************************************************************************\
  2. * npkmp.c - notepad Knuth-Morris-Pratt pattern matching
  3. *
  4. * Created by Microsoft Corporation, 1989
  5. \***************************************************************************/
  6.  
  7. #define INCL_WIN
  8. #include <os2.h>
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <opendlg.h>
  12. #include "notepad.h"
  13. #include "npkmp.h"
  14.  
  15. /************* PROCEDURE DECLARATIONS   */
  16.  
  17. VOID KMPCompileKey(char str[], PCOMPILEDKEY pck)
  18. {
  19.         STATE i,j;
  20.  
  21.         pck->key[0] = ' ';
  22.         lstrcpy(&(pck->key[1]),str);
  23.         pck->fail[0] = 0;
  24.         pck->fail[1] = 0;
  25.         for (j = 2; pck->key[j]; j++) {
  26.                 i = pck->fail[j-1];
  27.                 while ((pck->key[j] != pck->key[i+1]) && (i > 0))
  28.                         i = pck->fail[i];
  29.                 if ((pck->key[j] != pck->key[i+1]) && (i == 0))
  30.                         pck->fail[j] = 0;
  31.                 else
  32.                         pck->fail[j] = i+1;
  33.         }
  34.         pck->final = j-1;
  35. }
  36.  
  37.  
  38. static STATE delta(STATE j, char b, PCOMPILEDKEY pck)
  39. {
  40.         if (b == pck->key[j+1])
  41.                 return j+1;
  42.         else if (j == 0)
  43.                 return 0;
  44.         else
  45.                 return delta(pck->fail[j], b, pck);
  46. }
  47.  
  48. BOOL KMPMatchKey(PFNNEXT next, PCOMPILEDKEY pck, PULONG pcChar)
  49. {
  50.         STATE j;
  51.         ULONG pos;
  52.         char c;
  53.  
  54.         pos = 0;
  55.         j = 0;
  56.  
  57.         do {
  58.                 c = next();
  59.                 j = delta(j,c,pck);
  60.                 pos++;
  61.         } while ((c) && (j != pck->final));
  62.  
  63.         if (j == pck->final) {
  64.                 *pcChar = pos;
  65.                 return TRUE;
  66.         } else {
  67.                 *pcChar = 0;
  68.                 return FALSE;
  69.         }
  70. }
  71.  
  72.