2010/07/21 10:10

KMP String Matching Algorithm


KMP String Matching Algorithm is well-known algorithm for faster string search. KMP is, as you know, Knuth, Morris, and Pratt. It's complexity is O(n). n is the length of target string and O is big-O notation.

Here's the implemented algorithm.

////////////////////////////////////////////////////////////////////
// programmed by Kurapa Chunun Kang (kurapa@kurapa.com)
#ifndef __GLOBAL_H__
#define __GLOBAL_H__
 
#define MAX_STRING_SIZE                        100
#define MAX_PATTERN_SIZE                     100
 
int g_failure[MAX_PATTERN_SIZE];
int pattern_matching(char *str, char *pat);
void make_failure(char *pat);                                      

//////////////////////////////////////////////////////////////
#endif // __GLOBAL_H__
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
// Knuth,Morris,Pratt String Matching Algorithm
int pattern_matching(char *str, char *pat)
{
        int i = 0, j = 0;  // index
        int intStrLen = strlen(str);
        int intPatLen = strlen(pat);

        // debug
        // printf("intStrLen = %d intPatLen = %d\n", intStrLen, intPatLen);
 
        // index should be longer than intStrLen & intPatLen
        while ((i < intStrLen) && (j < intPatLen))
        {
               if (str[i] == pat[j])
               {
                       i++;
                       j++;
               }
               else if (j == 0) i++;
               else j = g_failure[j-1] + 1;
        }
        return ((j == intPatLen) ? (i - intPatLen) : -1);
}
 
void make_failure(char *pat) // create failure function for target string
{
        int j = 0;
        int intPatLen = strlen(pat);
        g_failure[j] = -1; // the first value should be -1

        int i = 0;
        for ( j=1; j<intPatLen; j ++)
        {
               i = g_failure[j - 1];
               while ((pat[j] != pat[i+1]) && (i >= 0))
               {
                       i = g_failure[i];
               } /// end while

               if (pat[j] == pat[i+1]) g_failure[j] = i+1;
               else g_failure[j] = -1;
        } // end for


        // below is for debug
        printf( "g_failure[]={");
        for (j = 0; j < intPatLen; j ++)
        {
            if (j) printf( ",%d", g_failure[j]);
            else printf("%d", g_failure[j]);
        }
        printf( "} - where pattern=%s\n", pat);

}

int main(int argc, char **argv)
{
        char string[] = "aababaaasdasdasdasdcas";
        char *pattern = "ababaa";
        int result = 0;
 
        make_failure(pattern);
 
        result = pattern_matching(string, pattern);
        // debug
        printf ("string is %s \n", string);
        printf ("pattern is %s \n", pattern);
        printf ("result = %d \n", result);


        make_failure(pattern);

        pattern = "aabba";
        make_failure(pattern);

        pattern = "abababab";
        make_failure(pattern);

        pattern = "ababbaab";
        make_failure(pattern);

        return 0;
}

/* run result
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

Z:\내 문서\Debug>KMP
g_failure[]={-1,-1,0,1,2,0} - where pattern=ababaa
intStrLen = 22 intPatLen = 6
string is aababaaasdasdasdasdcas
pattern is ababaa
result = 1
g_failure[]={-1,-1,0,1,2,0} - where pattern=ababaa
g_failure[]={-1,0,-1,-1,0} - where pattern=aabba
g_failure[]={-1,-1,0,1,2,3,4,5} - where pattern=abababab
g_failure[]={-1,-1,0,1,-1,0,0,1} - where pattern=ababbaab

Z:\내 문서\Debug>
*/

Trackback 0 Comment 0

Trackback : Cannot send a trackbact to this post.

2010/06/22 17:01

How to get browser information in PHP?


PHP provides to get Browser Information by function. Below is the simple example.

<?php
echo $_SERVER['HTTP_USER_AGENT'] . "\n\n";
?>


Above example may display as following, if you use FireFox.

Mozilla/5.0 (Windows; U; Windows NT 5.1; ko; rv:1.9.2.3) Gecko/20100401 Firefox/3.6.3 ( .NET CLR 3.5.30729)

In order to get above variable on function, you need to declare on top of the function as below.

function foo()
{
  global $_SERVER;

  echo $_SERVER['HTTP_USER_AGENT'];
}

Trackback 0 Comment 0

Trackback : Cannot send a trackbact to this post.

2010/04/14 13:28

Thread Application Implementation in TThread


Delphi provides class for thread application as TThread.

Following is the simple example for thread application.

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    GroupBox1: TGroupBox;
    seTimeToWork: TSpinEdit;
    Label1: TLabel;
    btnCreate: TButton;
    btnTerminate: TButton;
    procedure FormShow(Sender: TObject);
    procedure btnCreateClick(Sender: TObject);
    procedure btnTerminateClick(Sender: TObject);

  private
    FThread:TThread;
    procedure EnableButtons;
    procedure OnTerminate(Sender:TObject);
end;

TMyThread=class(TThread)
    private
      FTimeToWork:integer;
    protected
      procedure Execute;override;
    public
      constructor Create(TimeToWork:integer);
end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

// TMyThread

constructor TMyThread.Create(TimeToWork: integer);
begin
  FTimeToWork:=TimeToWork;
  inherited Create(True);
end;

procedure TMyThread.Execute;
var
  T:Integer;
begin
  t:=FTimeToWork;
  Form1.Memo1.Lines.Add('Begin execution');
  while not Terminated and (t>0) do
  begin
    Form1.Memo1.Lines.Add(format('Remaining %5.2f%%',[t/FTimeToWork*100]));
    Sleep(500);
    dec(t,500);
  end;

  if Terminated then
    Form1.Memo1.Lines.Add('Terminated by user');

  Form1.Memo1.Lines.Add('Finish execution');
end;

// TForm1
procedure TForm1.EnableButtons;
begin
  btnCreate.Enabled:=not Assigned(FThread);
  btnTerminate.Enabled:= Assigned(FThread);
end;

procedure TForm1.FormShow(Sender: TObject);
begin
  EnableButtons;
end;

procedure TForm1.btnCreateClick(Sender: TObject);
begin
  FThread:=TMyThread.Create(seTimeToWork.Value);
  FThread.OnTerminate:=OnTerminate;
  EnableButtons;
  FThread.Resume;
end;

procedure TForm1.btnTerminateClick(Sender: TObject);
begin
  FThread.Terminate;
end;

procedure TForm1.OnTerminate(Sender: TObject);
begin
  FThread:=nil;
  EnableButtons;
end;

end.




Trackback 0 Comment 0

Trackback : Cannot send a trackbact to this post.

2009/11/27 16:28

PHP function converts new line to BR tag


In case of displaying normal text having CR+LF character string on web browser, you may need to change it to <BR> tag.

PHP provides speedy converting function for supporting that. Following function is very useful.

Proto-type:
function nl2br( <source string> )

As you can expect by function name, it converts new line character set to <BR> tag.

Example)

.
.
.
$buf = nl2br( $source_string);
echo $buf;

1 Comment 0

Trackback : Cannot send a trackbact to this post.

  1. Subject Phentermine cheap.

    Tracked from Cheap phentermine. 2010/05/28 16:31 delete

    Phentermine cheap. Buy cheap phentermine online. Cheap phentermine online. Cheap phentermine cod. Cheap phentermine diet pill.

2009/10/19 16:01

PHP socket programming to get content with post method


When you need to get content with POST Method in PHP internal code, you need to get the desired result through alternate Socket Programming as below.

Actualluy what I wanted is emailing through alternate server located in different domain, because the current server has some limitation.

Following code is implemented at caller server.
<?
// caller page : kmail.php
// programmed by Super Coder / Chunun Kang (kurapa@kurapa.com)
function kmail( $recipient, $subject, $body)
{
  $host = "foo.com";
  $uri = "/api/kmail_api.php";

  // acutally security code is removed on below code.
  // you can add it by yourself.
  $reqbody = "s=" . urlencode($subject)
           . "&b=" . urlencode($body)
           . "&f=" . urlencode('SAMSUNGDForum')
           . "&h=" . urlencode($headers)
           . "&r=" . urlencode($recipient);

  $contentlength = strlen($reqbody);
  $reqheader = "POST $uri HTTP/1.0\xd\xa".
  "Host: $host\xd\xa". "User-Agent: Mozala\xd\xa".
  "Content-Type: application/x-www-form-urlencoded\xd\xa".
  "Content-Length: $contentlength\xd\xa\xd\xa".
  "$reqbody\xd\xa";
  $socket = fsockopen($host, 80, $errno, $errstr);
  if (!$socket)
  {
    $result["errno"] = $errno;
    $result["errstr"] = $errstr;
    return $result;
  }
  fputs($socket, $reqheader);
  while (!feof($socket))
  {
    $result[] = fgets($socket, 4096);
  }
  fclose($socket);
  return $result;
}
?>


In addition you need to add following callee PHP page on your callee server.
<?
    // callee page : /api/kmail.php
    // programmed by Super Coder / Chunun Kang (kurapa@kurapa.com)

    $title = '=?utf-8?b?'.base64_encode($s).'?=';
    $recipient = $r;

    if (strlen($h)<1)
    {
      if (strlen($f)>0)
      {
        $h = "From: $f <no-reply@foo.com>\r\n";
      }
      else
      {
        $h = "From: NO-REPLY <no-reply@foo.com>\r\n";
      }
      $h .= "X-Sender: no-reply@foo.com\r\n";
      $h .= "X-Mailer: Mozala PHP ".phpversion()."\n";
    }
   
    mail($recipient , $title, $b, $h);
?>


Finally what you need to do is including above caller page to call kmail function.

include "./kmail.php";
kmail( "foo@foo.com", "howdy?", "test message from Chunun Kang (kurapa@kurapa.com");

Trackback 0 Comment 0

Trackback : Cannot send a trackbact to this post.