Solved

Searching a string?

Posted on 1998-04-25
7
204 Views
Last Modified: 2010-04-06
I have a set of strings (actually pchars)
each is approximately 1100 characters long I wish to search these for a substring of about 20 characters.
what is the most efficient way of doing this,
whilst allowing for maybe one or two mismatches within the substring?

many thanks
john
0
Comment
Question by:John Culkin
7 Comments
 
LVL 4

Expert Comment

by:d003303
ID: 1336968
Yo,
have you tried the StrPos function ? It is pretty fast.

Slash/d003303
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1336969
The StrPos() works fine for exact matches.
To handle mismatches you need some code.

Say you wish to allow for M=2 mismatches.

Basically you have to compare chars one at a time, check for matching chars at the given max dinstance M, and keep considering a possible string match until the sum of distances does not exceed M. If you reach the end of the matching string, then you have a string match. You must also be prepared to follow more than one possibility at a time: actually you need to handle up to M+1 parallel checks.

If this sounds like what you're looking for, i can provide the needed code in a couple of days. If this is the case, please also tell wether you'd like a function accepting M as a parameter, or you just need M to be fixed and equal to... 2?

Regards.
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1336970
Another, simpler but maybe slower (?) way, is to take your matching string and generate all the possible derivated matching strings - at distance <= M -, and test with StrPos() for each of them. Maybe is this what d003303 meant?

In case you ask for an answer, i'll try to compute which is faster first, and will answer accordingly.

d003303, feel free to consider the question anyway open in the meantime :)
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
LVL 4

Expert Comment

by:d003303
ID: 1336971
Hi julio,
right, that's what I thought. But if M or the length of the substring will raise, this solution will be no fun anymore. Best would be your algorithm that takes the mismatch parameter, otherwise (when the profile of the app is changing) you'll  have to re-code everything.

Slash/d003303
0
 
LVL 8

Expert Comment

by:ZifNab
ID: 1336972
Hi John,

A while ago, somebody already answered such a question, so it can be handy to browse through the answered questions...

Also very handy can be an article of the Delphi Informant magazine of March '98...

Regards, ZiF.
0
 
LVL 5

Accepted Solution

by:
inter earned 200 total points
ID: 1336973
Hi there, here is my routine I code and try to test it as much as I can. It works as follows: give a substring, string, and max mismatch it returns nil if not found else returns a pointer to the matching string starting position:
e.g.
StrCopy(SubStr,  'mello');
StrCopy(Str, 'who the hell are those man saying hello');
PartialPos(SubStr, Str, 1) returns pointer to 'hello' in Str
PartialPos(SubStr, Str, 2) returns pointer to 'hell ...' in Str
NOTE : DO NOT MODIFY THE CONTENT OF THE RETURN VALUE IT JUST POINTS TO YOUR Str so copy it if you want to modify it!

function PartialPos(S, D :PChar; M:integer):PChar;
  function ComputeMismatch(S,D : PChar):integer;
  begin
    Result := 0;
    while (S^ <> #0) and (D^ <> #0) do
    begin
      if S^ <> D^ then Inc(Result);
      Inc(S); Inc(D);
    end;
    // we have end of D but still there are chars in S!
    if S^ <> #0 then Inc(Result, StrLen(S));
  end;
var
  P : PChar;
  Done : boolean;
  L : integer;
begin
  Result := nil; Done := false; L := StrLen(S);
  // If predefined conditions set terminate search
  if (StrLen(S) > StrLen(D)) or (StrLen(S) < M) then EXIT;
  if M = 0 then begin Result := StrPos(D, S); Exit;end;
  while not Done and (S^ <>#0) do
  begin
    P := StrScan(D, S^);
    if P <> nil then
    begin
        while P <> nil do
        begin
          if ComputeMismatch(S, P) <= M then
          begin
           Done := True;
           Result := P - (L - StrLen(S));
           if Result < D then Result := D;
           Break;
          end;
          P := StrScan(P+1, S^); //search other substring
        end;
        if not Done then begin Inc(S); Dec(M); end;
    end else begin //not found in
      Dec(M);
      Inc(S,1);
      if M < 0 then Done := true;
    end; // if P <> nil...
  end;
end;

Regards,
Igor
0
 

Author Comment

by:John Culkin
ID: 1336974
Thanks for so many replies
this routine does everything I need

Many Thanks


John
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Have you ever had your Delphi form/application just hanging while waiting for data to load? This is the article to read if you want to learn some things about adding threads for data loading in the background. First, I'll setup a general applica…
Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…
Access reports are powerful and flexible. Learn how to create a query and then a grouped report using the wizard. Modify the report design after the wizard is done to make it look better. There will be another video to explain how to put the final p…

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now