home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / c / 18958 < prev    next >
Encoding:
Text File  |  1992-12-29  |  1.3 KB  |  31 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!spool.mu.edu!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!s.psych.uiuc.edu!amead
  3. From: amead@s.psych.uiuc.edu (Alan Mead)
  4. Subject: ALGORITHM to flexibly match strings needed
  5. Message-ID: <C008DH.3I3@news.cso.uiuc.edu>
  6. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  7. Organization: UIUC Department of Psychology
  8. Date: Tue, 29 Dec 1992 04:56:04 GMT
  9. Lines: 20
  10.  
  11. Someone suggested that programmers here were, shall we say
  12. exceptionally "with it"?  Anyway, although this has nothing to do with
  13. C per se, I'd like to know about any algorithms for matching strings.
  14. Specifically, I need to count typos in a sample string as compared to a
  15. target string.  Obviously, I cannot just compare each char as an
  16. initial additional stroke would cause numerous, erroneous errors.  Eg,
  17. " Run Spot run." as a sample of "Run Spot run." is one error, not 13.
  18.  
  19. I've gotten as far as conceptualizing it as "sliding" the mis-matching
  20. sub-string of the sample string left and right in increasing amounts
  21. until a match is made, but I just cannot imagine how to code such a beast.
  22.  
  23. I imagine that this algorithm would be analogous to that used by UNIX
  24. diff.  I don't know how smart that utility is, but you wouldn't want to
  25. declare two files completely dissimilar simpily because one was
  26. preceeded by a blank line.
  27.  
  28. Thanks for any sugestions.
  29.  
  30. -alan mead
  31.