\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Parallel String Matching with Multi Core Processors-A Comparative Study for Gene Sequences},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2013-01-15 (revised: 15 January 2013)}
\def\TheID{\makeatother }
\def\TheDate{2013-01-15}
\title{Parallel String Matching with Multi Core Processors-A Comparative Study for Gene Sequences}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Chinta Someswara  Rao}

             \affil[1]{  SRKR Engineering College affiliated to Andhra University}

\renewcommand\Authands{ and }

\date{\small \em Received: 13 December 2012 Accepted: 3 January 2013 Published: 15 January 2013}

\maketitle


\begin{abstract}
        


The increase in huge amount of data is seen clearly in present days because of requirement for storing more information. To extract certain data from this large database is a very difficult task, including text processing, information retrieval, text mining, pattern recognition and DNA sequencing. So we need concurrent events and high performance computing models for extracting the data. This will create a challenge to the researchers. One of the solutions is parallel algorithms for string matching on computing models. In this we implemented parallel string matching with JAVA Multi threading with multi core processing, and performed a comparative study on Knuth Morris Pratt, Boyer Moore and Brute force string matching algorithms. For testing our system we take a gene sequence which consists of lacks of records. From the test results it is shown that the multicore processing is better compared to lower versions. Finally this proposed parallel string matching with multicore processing is better compared to other sequential approaches.

\end{abstract}


\keywords{string matching; parallel string mathing; computing model, DNA, multicore processing.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{INTRODUCTION}]{INTRODUCTION}\par
he crisis of finding exact or non-exact occurrences of a pattern P in a text T over some alphabet is a central difficulty of combinatorial string matching and has a variety of applications in many areas of computer science  {\ref [1]}\hyperref[b1]{[2]}\hyperref[b2]{[3]}. String searching algorithms can be accomplished in two ways: 1. Exact match, meaning that the passages returned will contain an exact match of the key input. 2. Approximate match, meaning that the passage will contain some part of the key word input \hyperref[b3]{[4]}\hyperref[b4]{[5]}\hyperref[b5]{[6]}.\par
Although the dramatic development of processor technology and other advances have reduced search response to negligible times, string matching problem still remains a useful area of research and development for a number of reasons. Initially, as the size of data continues to grow, sequence searches will become increasingly taxing on search engines. Secondly, the pattern matching still remains an integral part of faster matching algorithms, typically comprising the final part of a search. Finally, researchers have to understand the classical methods of pattern matching to develop new efficient algorithms \hyperref[b6]{[7]}\hyperref[b7]{[8]} {\ref [9]} {\ref [10]}.\par
With the developments of new string matching techniques, efficiency and speed are the main factors in deciding among different options available for each application area. Each application area has certain special features that can be used by string matching technique best suited for that area \hyperref[b8]{[11]} {\ref [12]} {\ref [13]}. This study implements a multithreading text searching approach to improve text searching performance at a multicore processing. The idea is to have more than one searcher thread that search the text from different positions. Since the required pattern may occur at any position, having multiple searchers is better than searching the text sequentially from the first character to the last one.\par
The main contributions of this work are summarized as follows. This work offers a comprehensive study as well as the results of typical parallel string matching algorithms at various aspects and their application on multicore computing models. This work suggests the most efficient algorithmic models and demonstrates the performance gain for both synthetic and real data. The rest of this work is organized as, review typical algorithms, algorithmic models and finally conclude the study. 
\section[{II.}]{II.} 
\section[{RELATED WORK}]{RELATED WORK}\par
Now a day's information retrieval attracted by the many researchers because of their importance in IT industry. So, this many researchers worked on this area since several years. In this paper we propose some of the techniques comparisons with multicore processing. In this section we discuss some previous techniques proposed by several authors' later section we will discuss about our actual procedure. S.V. Raju et.al \hyperref[b9]{[14]} proposes about grid computing in parallel string matching. Grid computing provides solutions for various complex problems. The function of the grid is to parallelize the string matching problem using grid MPI parallel programming method or loosely coupled parallel services on Grid. Parallel applications fall under three categories namely Perfect parallelism, Data parallelism and Functional parallelism, use data parallelism, and it is also called Single Program Multiple Data (SPMD) method, where given data is divided into several parts and working on the part simultaneously. 
\section[{Perfect Parallelism}]{Perfect Parallelism}\par
Also known as embarrassingly parallel. An application can be divided into sets of processes that require little or no communication. 
\section[{Data Parallelism}]{Data Parallelism}\par
The same operation is performed on many data elements simultaneously. An example would be using multiple processes to search different parts of a database for one specific query.\par
Functional parallelism: Often called control parallelism. Multiple operations are performed simultaneously, with each operation addressing a particular part of the problem. 
\section[{Result}]{Result}\par
Here it shows the performance of string matching algorithms namely execution-time and speedup improved.\par
HyunJin Kim and Sungho Kang \hyperref[b10]{[15]} propose an algorithm that partitions a set of target patterns into multiple subgroups for homogeneous string matchers. Using a pattern grouping metric, the proposed pattern partitioning makes the average length of the mapped target patterns onto a string matcher approximately equal to the average length of total target patterns. The target architecture is based on a memory-based string matching with homogeneous string matchers. In a string matcher, ?? homogeneous finite state machine (FSM) tiles are contained. An FSM tile contains a maximum of ?? states and takes ?? bits of one character at each cycle. Target patterns are distributed and mapped onto ?? string matchers. Each state has 2?? pointers for the next state based on an ??-bit input. 
\section[{Result}]{Result}\par
By adopting the pattern grouping metric, the proposed pattern group partitioning decreases the number of adopted string matchers by balancing the numbers of mapped target patterns between string matchers.\par
Daniel Luchaup, et.al \hyperref[b11]{[16]} they propose a method to search for arbitrary regular expressions by scanning multiple bytes in parallel using speculation. They break the packet in several chunks, opportunistically scan them in parallel, and if the speculation is wrong, correct it later. They present algorithms that apply speculation in single-threaded software running on commodity processors as well as algorithms for parallel hardware. 
\section[{Result}]{Result}\par
It is a speculative pattern matching method which is a powerful technique for low latency regularexpression matching. The method is based on three important observations. The first key insight is that the serial nature of the memory accesses is the main latency-bottleneck for a traditional DFA matching. The second observation is that a speculation that does not have to be right from the start can break this serialization The third insight, which makes such a speculation possible, is that the DFA-based scanning for the intrusion detection domain spends most of the time in a few hot states.\par
Hyun Jin Kim, et.al \hyperref[b12]{[17]} propose a memoryefficient parallel string matching scheme. In order to reduce the number of state transitions, the finite state machine tiles in a string matcher adopt bit-level input symbols. Long target patterns are divided into sub patterns with a fixed length; deterministic finite automata are built with the sub patterns. Using the pattern dividing, the variety of target pattern lengths can be mitigated, so that memory usage in homogeneous string matchers can be efficient. 
\section[{Result}]{Result}\par
The proposed DFA-based parallel string matching scheme minimizes total memory requirements. The problem of various pattern lengths can be mitigated by dividing long target patterns into sub patterns with a fixed length. The memory-efficient bit-split FSM architectures can reduce the total memory requirements. Considering the reduced memory requirements for the real rule sets, it is concluded that the proposed string matching scheme is useful for reducing total memory requirements of parallel string matching engines.\par
Charalampos S, et.al \hyperref[b13]{[18]} they proposes that Graphics Processing Units (GPUs) have evolved over the past few years from dedicated graphics rendering devices to powerful parallel processors, outperforming traditional Central Processing Units (CPUs) in many areas of scientific computing. The use of GPUs as processing elements was very limited until recently, when the concept of General-Purpose Computing on Graphics Processing Units (GPGPU) was introduced. GPGPU made possible to exploit the processing power and the memory bandwidth of the GPUs with the use of APIs that hide the GPU hardware from programmers. This paper presents experimental results on the parallel processing for some well known on-line string matching algorithms using one such GPU abstraction API, the Compute Unified Device Architecture (CUDA). 
\section[{Result}]{Result}\par
In this, both the serial and the parallel implementations were compared in terms of running time for different reference sequences, pattern sizes and number of threads. It was shown that the parallel implementation of the algorithms was up to 24x faster than the serial implementation, especially when larger text and smaller pattern sizes where used. The performance achieved is close to the one reported for similar string matching algorithms. In addition, it was discussed that in order to achieve peak performance on a GPU, the hardware must be as utilized as possible and the shared memory should be used to take advantage of its very low latency. Future research in the area of string matching and GPGPU parallel processing could focus on the performance study of the parallel implementation of additional categories of string matching algorithms, including approximate and two dimensional string matching.\par
Thierry Lecroq \hyperref[b14]{[19]} propose a very fast new family of string matching algorithms based on hashing q-grams. The new algorithms are the fastest on many cases, in particular, on small size alphabets. The string matching problem consists in finding one or more usually all the occurrences of a pattern x = x[0..m ? 1] of length m in a text y = y[0..n ? 1] of length n. It can occur, for instance, in information retrieval, bibliographic search and molecular biology. 
\section[{Result}]{Result}\par
In this article they presented simple and though very fast adaptations and implementations of the Wu-Manber exact multiple string matching algorithm to the case of exact single string matching algorithm. Experimental results show that the new algorithms are very fast for short patterns on small size alphabets comparing to the well known fast algorithms using bitwise techniques. The new algorithms are also fast on long patterns (length 32 to 256) comparing to algorithms using an indexing structure for the reverse pattern (namely the Backward Oracle Matching algorithm). This new type of algorithm can serve as filters for finding seeds when computing approximate string matching.\par
Derek Pao, et.al \hyperref[b15]{[20]} proposes that a memoryefficient hardware string searching engine for antivirus applications is presented. The proposed QSV method is based on quick sampling of the input stream against fixed-length pattern prefixes, and on-demand verification of variable-length pattern suffixes. Patterns handled by the QSV method are required to have at least 16 bytes, and possess distinct 16-byte prefixes. The latter requirement can be fulfilled by a preprocessing procedure. The search engine uses the pipelined Aho-Corasick (P-AC) architecture developed by the first author to process 4 to 15-byte short patterns and a small number of exception cases. Our design was evaluated using the Clam AV virus database having 82,888 strings with a total size that exceeds 8 MB. In terms of byte count, 99.3 percent of the pattern set is handled by the QSV method and 0.7 percent of the pattern set is handled by P-AC. A pattern with distinct 16-byte prefix only occupies up to three lookup table entries in QSV. The overall memory cost of our system is about 1.4 MB, i.e., 1.4 bit per character of the ClamAV pattern set. The proposed method is memory-based, hence, updates to the pattern set can be accommodated by modifying the contents of the lookup tables without reconfiguring the hardware circuits.\par
Hassan Ghasemzadeh  {\ref [21]} proposes that Mobile sensor-based systems are emerging as promising platforms for healthcare monitoring. An important goal of these systems is to extract physiological information about the subject wearing the network. Such information can be used for life logging, quality of life measures, fall detection, extraction of contextual information, and many other applications. Data collected by these sensor nodes are overwhelming, and hence, an efficient data processing technique is essential. 
\section[{Result}]{Result}\par
Results show the effectiveness of this approach, both for reliable movement classification and reduction of communication.\par
HyunJin Kim and Seung-Woo Lee \hyperref[b16]{[22]} propose a memory-based parallel string matching engine using the compressed state transitions. In the finite-state machines of each string matcher, the pointers for representing the existence of state transitions are compressed. In addition, the bit fields for storing state transitions can be shared. Therefore, the total memory requirement can be minimized by reducing the memory size for storing state transitions Result This letter proposed a memory-efficient parallel string matching engine in DFA-based string matching. The proposed string matcher can reduce the memory size for storing the existence of state transitions. In addition, the memory requirements can be reduced by sharing state transitions in the transition table. Considering the experiment results, it is evident that the proposed architecture is useful for reducing the storage cost of the DFA-based string matching engine. Ali Peiravi and Mohammad Javad Rahimzadeh \hyperref[b17]{[23]} proposes that String matching is a fundamental element of an important category of modern packet processing applications which involve scanning the content flowing through a network for thousands of strings at the line rate. To keep pace with high network speeds, specialized hardware-based solutions are needed which should be efficient enough to maintain scalability in terms of speed and the number of strings. In this paper, a novel architecture based upon a recently proposed data structure called the Bloomier filter is proposed which can successfully support scalability. The Bloomier filter is a Compact data structure for encoding arbitrary functions, and it supports approximate evaluation queries. By eliminating the Bloomier filter's false positives in a space efficient way, a simple yet powerful exact string matching architecture is proposed that can handle several thousand Strings at high rates and is amenable to onchip realization. The proposed scheme is implemented in reconfigurable hardware and compare it with existing solutions. The results show that the proposed approach achieves better performance compared to other existing architectures measured in terms of throughput per logic cells per character as a metric.\par
In this paper, we use parallel algorithms with multicore processors because with multicore processors we can increase the efficiency and the performance. 
\section[{III. COMPUTING MODEL WITH MULTICORE PORCESSING}]{III. COMPUTING MODEL WITH MULTICORE PORCESSING}\par
As personal computers have become more prevalent and more applications have been designed for them, the end-user has seen the need for a faster, more capable system to keep up. Speedup has been achieved by increasing clock speeds and, more recently, adding multiple processing cores to the same chip. Although chip speed has increased exponentially over the years, that time is ending and manufacturers have shifted toward multicore processing. However, by increasing the number of cores on a single chip challenges arise with memory and cache coherence as well as communication between the cores. Coherence protocols and interconnection networks have resolved some issues, but until programmers learn to write parallel applications, the full benefit and efficiency of multi core processors will not be attained \hyperref[b18]{[24]}\hyperref[b19]{[25]}\hyperref[b20]{[26]}\hyperref[b21]{[27]}. 
\section[{IV.}]{IV.}\par
PROPOSED SYSTEM ARCHITECTURE a) System Architecture System Architecture describes "the overall structure of the system and the ways in which the structure provides conceptual integrity". Architecture is the hierarchical structure of a program components (modules), the manner in which these components interact and the structure of data that are used by that components. The existing string matching system architecture is as shown in Fig 1 and in this the efficiency is not good. In the existing string matching architecture we search the required pattern sequentially at first we pass the required that is to be searched and this pattern is searched by using the three algorithms Brute force, KMP, Boyer Moore the entire string is passed through all the algorithms and the output match and the running time is calculate for the required pattern from all the algorithms and the algorithm with the least running time is selected, all this is done sequentially which takes more time to execute to improve the efficiency and the performance in this we use the parallel string matching algorithms with multicores processors as shown in Fig 2.\par
The proposed system Architecture of Comparison of parallel String Matching Algorithms is as follows in the below diagram. In this search the pattern parallel. in this at first we take the input as a string or text. The required text that is to be searched is further divided into further small patterns and all this patterns are passed on the different parallel algorithms like KMP  
\section[{BM Algorithm}]{BM Algorithm} 
\section[{BF Algorithm}]{BF Algorithm} 
\section[{Output match positions and running time}]{Output match positions and running time} 
\section[{Output match positions and running time}]{Output match positions and running time} 
\section[{Browse file and enter pattern}]{Browse file and enter pattern} 
\section[{Comparison KMP Algorithm}]{Comparison KMP Algorithm} 
\section[{Output match positions and running time}]{Output match positions and running time}\par
boyar Moore, brute force and at all the output position match and running time of all the patterns is calculated and the all the patterns of same algorithm are added and all the resulted running time are compared with other algorithms resulting time and from them the best one is taken as the efficient algorithm for the string matching.  
\section[{PROPOSED APPROACH}]{PROPOSED APPROACH}\par
In now a day as the current free textual database is growing vast there is a problem of finding the pattern by string matching the efficiency is decreased and takes more time. In our paper, we use parallel algorithms to increase the efficiency on multicore processor we pass the same string to all the three algorithms and we select the best based on the running time. 
\section[{a) Implementation}]{a) Implementation}\par
Here we have to implement the proposed system with JAVA 1.7 multi threading, initially we have to implement the BF, KMP, and BM sequentially and then go for parallel implementation with threading on Multicore processor. Here we discuss some of them.\par
i. Brute force Algorithm (BF) description and Implementation with parallel programming \hyperref[b22]{[28]}\hyperref[b23]{[29]}\hyperref[b25]{[30]} The brute force algorithm consists in checking, at all positions in the text between 0 and n -m. whether an occurrence of the pattern starts there or not. Then, after each attempt, it shifts the pattern by exactly one position to the right. The brute force algorithm requires no preprocessing phase, and a constant extra space in addition to the pattern and the text. During the searching phase the text character comparisons can be done in any order. The algorithm can be designed to stop on either the first occurrence of the pattern, or upon reaching the end of the text. This code was run parallel in multiple threads to achieve good efficiency searching, which is shown in Table  {\ref 1}. ii. Knuth Morris Pratt description and Implementation with parallel programming \hyperref[b22]{[28]}\hyperref[b23]{[29]}\hyperref[b25]{[30]} Consider an attempt at a left position j, that is when the window is positioned on the text factor y[j .. j+m-1]. Assume that the first mismatch occurs between x [i] and y [i+j] with 0 < i < m. Then, x[0 .. i-1] = y[j .. i+j-1]=u and a = x [i] ? y [i+j]=b. When shifting, it is reasonable to expect that a prefix v of the pattern matches some suffix of the portion u of the text. Moreover, if we want to avoid another immediate mismatch, the character following the prefix v in the pattern must be different from a. The longest such prefix v is called the tagged border of u. This code was run parallel in multiple threads to achieve good efficiency searching, which is shown in Table  {\ref 2}. The algorithm scans the characters of the pattern from right to left beginning with the rightmost one. In case of a mismatch (or a complete match of the whole pattern) it uses two precomputed functions to shift the window to the right. These two shift functions are called the good-suffix shift (also called matching shift) and the bad-character shift (also called the occurrence shift). This code was run parallel in multiple threads to achieve good efficiency searching, which is shown in Table  {\ref 3}.\par
Table  {\ref 3} : Pseudo code for BM FileInputStream fstream = new FileInputStream("F:/multi/genesequence.txt"); DataInputStream in = new DataInputStream(fstream); BufferedReader br = new BufferedReader(new InputStreamReader(in)); time = System.currentTimeMillis(); while ( ((str = br1.readLine()) != null) \&\& (i<=i1) )\{ BoyerMoore bms = new BoyerMoore(); String pattern = "AAGG"; bms.setString(str, pattern); first\textunderscore occur\textunderscore position = bms.search(); System.out.println("The text '" + pattern + "' is first found after the " + first\textunderscore occur\textunderscore position + " position."); i++;\} time System.currentTimeMillis() -time; System.out.println("Time elapsed-in thread-1"+time); b) Claims Implementation is the stage where the theoretical design is turned into a working system. The most crucial stage in achieving a new successful system and in giving confidence on the system for the users that will work efficiently and effectively. The system will be implemented only after thorough testing and if it is found to work according to the specification. For testing our proposed system we will take the gene sequence data set, consists of the four nucleotides a, c, g and t (standing for adenine, cytosine, guanine, and thymine, respectively) used to encode DNA. Therefore, the alphabet is O=\{A, C, G, T\}. The text is consisted of 7,50,000 records. Our test tested with different processors like i3, i5 etc., here we put some achievements what we develop and observe, finally our system shows that parallel approach is much better than sequential approach with multi core processor The Fig  {\ref 3} shows(Graph) Execution time vs File size on sequential search with intel i5 processor using Boyer Moore, Brute force, KMP Algorithm. From the graph we clearly observe that BM is better compared to other approaches.   
\section[{CONCLUSIONS}]{CONCLUSIONS}\par
In this paper we performed a comparative study on Knuth Morris Pratt, Boyer Moore and Brute force string matching algorithms based on the running time and in our tests with multicore processing, we used strings of varying lengths and texts of varying lengths. From the test results it is shown that the Boyer Moore algorithm is extremely efficient in most cases and Knuth-Morris-Pratt algorithm is not better on the average than the Brute force algorithm. We conclude that Boyer Moore string matching algorithm is the most efficient one among the three string matching algorithms with multicore processing compared to earlier versions. As a future enhancement, these algorithms can be compared with other efficient parallel string matching algorithms thereby finding the most efficient algorithm which can be used in many fields such as cryptography, molecular biology. Thus the problem of matching becomes easier. This page is intentionally left blank\begin{figure}[htbp]
\noindent\textbf{2013}\includegraphics[]{image-2.png}
\caption{\label{fig_0}T © 2013}\end{figure}
         \begin{figure}[htbp]
\noindent\textbf{} \par 
\begin{longtable}{P{0.05405405405405405\textwidth}P{0.08378378378378377\textwidth}P{0.05405405405405405\textwidth}P{0.11621621621621622\textwidth}P{0.15945945945945947\textwidth}P{0.05405405405405405\textwidth}P{0.05405405405405405\textwidth}P{0.08648648648648649\textwidth}P{0.05405405405405405\textwidth}P{0.13378378378378378\textwidth}}
\tabcellsep \tabcellsep \tabcellsep \multicolumn{2}{l}{Browse file (text) and}\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep enter pattern\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\tabcellsep \tabcellsep \tabcellsep \multicolumn{2}{l}{Divide text in to number}\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep of patterns\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
\tabcellsep 1 st pattern\tabcellsep \tabcellsep \tabcellsep 2 nd pattern\tabcellsep \tabcellsep \tabcellsep 3 rd pattern\tabcellsep \tabcellsep \\
BF algorithm (a1) found \& runnin g time\tabcellsep KMP algorithm (b1) found \& runnin g time\tabcellsep BM algorithm (c1) found \& runnin g time\tabcellsep BF algorithm (a2) found \& runnin g time\tabcellsep KMP algorithm (b2) found \& runnin g time\tabcellsep BM algorithm (c2) found \& runnin g time\tabcellsep BF algorithm (a3) found \& runnin g time\tabcellsep KMP algorithm (b3) found \& runnin g time\tabcellsep BM algorithm (c3) found \& runnin g time\tabcellsep Volume XIII Issue I Version I D D D D D D D D ) A\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep (\\
\tabcellsep a1+a2+?an\tabcellsep \tabcellsep \tabcellsep b1+b2+?bn Running Times comparison Output\tabcellsep \tabcellsep \tabcellsep c1+c2+?..cn\tabcellsep \tabcellsep Global Journal of Computer Science and Technology\end{longtable} \par
 
\caption{\label{tab_0}}\end{figure}
 			\footnote{© 2013 Global Journals Inc. (US)} 			\footnote{Parallel String Matching with Multi Core Processors-A Comparative Study for Gene Sequences} 			\footnote{© 2013 Global Journals Inc . (US)} 			\footnote{. Badoiu M. and Indyk P., "Fast Approximate Pattern Matching with Few Indels via Embeddings," ACM-© 2013 Global Journals Inc. (US)} 		 		\backmatter  			 			 			  				\begin{bibitemlist}{1}
\bibitem[Knuth]{b23}\label{b23} 	 		\textit{},  		 			Donald Knuth 		.  		 	 
\bibitem[Mhashi et al. ()]{b3}\label{b3} 	 		‘A Fast Approximate String Searching Algorithm’.  		 			M Mhashi 		,  		 			A Rawashdeh 		,  		 			A Hammouri 		.  	 	 		\textit{Computer Journal of Science Publication}  		2005. p. .  	 
\bibitem[Boyer and Moore ()]{b22}\label{b22} 	 		\textit{A fast string searching algorithm, Carom. Association of computing Machinary},  		 			R S Boyer 		,  		 			J S Moore 		.  		1977. p. .  	 
\bibitem[Kim and Lee ()]{b16}\label{b16} 	 		‘A Hardware-Based String Matching Using State Transition Compression for Deep Packet Inspection’.  		 			Hyunjin Kim 		,  		 			Seung-Woo Lee 		.  	 	 		\textit{ETRI Journal}  		2013. 35  (1)  p. .  	 
\bibitem[Kim et al. (2011)]{b2}\label{b2} 	 		‘A Memory-Efficient Bit-Split Parallel String Matching Using Pattern Dividing for Intrusion Detection Systems’.  		 			Hyun Jin Kim 		,  		 			Hong-Sik Kim 		,  		 			Sungho Kang 		.  	 	 		\textit{IEEE Transactions on Parallel and Distributed Systems}  		Nov. 2011. 22  (11)  p. .  	 
\bibitem[Hyunjinkim ()]{b12}\label{b12} 	 		‘A memory-efficient bitsplit parallel string matching using pattern dividing for intrusion detection systems’.  		 			Hyunjinkim 		.  	 	 		\textit{ieee transactions on parallel and distributed systems},  				2011. 22 p. .  	 
\bibitem[Kim et al. (2009)]{b1}\label{b1} 	 		‘A Memory-Efficient Parallel String Matching for Intrusion Detection Systems’.  		 			H Kim 		,  		 			H Hong 		,  		 			H.-S Kim 		,  		 			S Kang 		.  	 	 		\textit{IEEE Comm. Letters}  		Dec. 2009. 13  (12)  p. .  	 
\bibitem[Peiravi and Javed Rahimzadeh ()]{b17}\label{b17} 	 		\textit{A novel scalable and storage-efficient architecture for high speed exact string matching},  		 			Ali Peiravi 		,  		 			Mohammad Javed Rahimzadeh 		.  		2009. 31 p. .  	 
\bibitem[Kim and Kang ()]{b10}\label{b10} 	 		\textit{A pattern group partitioning for parallel string matching using a pattern grouping metric},  		 			Hyunjin Kim 		,  		 			Kang 		.  		2010. 14 p. .  	 	 (ieee communications letters) 
\bibitem[
			JonathanL
		 ()]{b6}\label{b6} 	 		\textit{Analysis of Fundamental Exact and Inexact Pattern Matching Algorithms},  		 			JonathanL 		.  		2004.  		 			Stanford University 		 	 	 (Technical Document) 
\bibitem[Breslauer et al. ()]{b4}\label{b4} 	 		‘Constant-Time word-size string matching’.  		 			Dany Breslauer 		,  		 			Leszek G?sieniec 		,  		 			Roberto Grossi 		.  	 	 		\textit{Proceedings of the 23rd Annual conference on Combinatorial Pattern Matching},  				 (the 23rd Annual conference on Combinatorial Pattern MatchingHelsinki, Finland)  		2012.  	 
\bibitem[Thierry Lecroq (2007)]{b14}\label{b14} 	 		\textit{Fast exact string matching algorithms", "litis, faculty des sciences et des techniques, university de rouen, 76821 mont-saintavignon cedex, france},  		 			Thierry Lecroq 		.  		january 2007.  	 
\bibitem[Morris et al. ()]{b24}\label{b24} 	 		‘Fast pattern matching in strings’.  		 			James H Morris 		,  		 			Vaughan Jr 		,  		 			Pratt 		.  	 	 		\textit{SIAM Journal on Computing}  		1977. p. .  	 
\bibitem[Leow and Ng ()]{b20}\label{b20} 	 		‘Generating hardware from OpenMP programs’.  		 			Y Leow 		,  		 			C \&w F Ng 		,  		 			W 		.  	 	 		\textit{International Conference on Field Programmable Technology},  				2006. p. .  	 
\bibitem[Pao ()]{b15}\label{b15} 	 		‘Hassan ghasemzadeh," structural action recognition in body sensor networks: distributed classification based on string matching’.  		 			Derek Pao 		.  	 	 		\textit{ieee transactions on information technology in biomedicine},  				2011. 2010. 60 p. .  	 	 (string searching engine for virus scanning) 
\bibitem[Grama et al. ()]{b19}\label{b19} 	 		\textit{Introduction to Parallel Computing},  		 			A Grama 		,  		 			G Karypis 		,  		 			V Kumar 		,  		 			A Gupta 		.  		2003. Addison Wesley.  	 
\bibitem[Marr et al. ()]{b21}\label{b21} 	 		 			D T Marr 		,  		 			F Binns 		,  		 			D L Hill 		,  		 			G Hinton 		,  		 			D A Koufaty 		,  		 			J A Miller 		,  		 			M Upton 		.  	 	 		\textit{Hyper-Threading Technology Architecture and Microarchitecture},  				2002. p. .  	 
\bibitem[Galil ()]{b25}\label{b25} 	 		‘Optimal parallel algorithms for string matching’.  		 			Z Galil 		.  	 	 		\textit{Proc. 16th Annu. ACM symposium on Theory of computing},  				 (16th Annu. ACM symposium on Theory of computing)  		1984. p. .  	 
\bibitem[Raju ()]{b9}\label{b9} 	 		‘parallel string matching algorithm using grid", "international journal of distributed and parallel systems’.  		 			S Raju 		.  	 	 		\textit{ijdps}  		2012. 3  (3) .  	 
\bibitem[Geist et al. ()]{b18}\label{b18} 	 		‘PVM: Parallel Virtual Machine’.  		 			A Geist 		,  		 			A Beguelin 		,  		 			J Dongarra 		,  		 			W Jiang 		,  		 			R \& V Manchek 		,  		 			S 		.  	 	 		\textit{A Users Guide and Tutorial for Networked Parallel Computing},  				1994. MIT Press.  	 
\bibitem[Someswararao et al. ()]{b7}\label{b7} 	 		‘Recent Advancement is Parallel Algorithms for String matching on computing models -A survey and experimental results’.  		 			Chinta Someswararao 		,  		 			Butchiraju 		,  		 			; Viswanadharaju 		,  		 			K Someswararao 		,  		 			Butchiraju 		,  		 			; K Viswanadharaju 		,  		 			S Butchiraju 		,  		 			Viswanadharaju 		.  	 	 		\textit{IEEE conference on Application of Information and Communication Technologies},  				2011. 2011. 2012. Springer. ISBN p. .  	 	 (IJAC) 
\bibitem[Simon et al. (2004)]{b8}\label{b8} 	 		‘Recent Advancement is String matching algorithms-A survey and experimental results’.  		 			Y Simon 		,  		 			M. ; K Inayatullah 		,  		 			S Butchiraju 		,  		 			; K Viswanadharaju 		,  		 			S Butchiraju 		,  		 			Viswanadharaju 		.  	 	 		\textit{Proceedings of Symposium on Principles and Practice of Programming in Java},  				 (Symposium on Principles and Practice of Programming in Java)  		2004. July -Sept, ISSN 2229-4333, 2012. 2013. 12 p. .  		 			IJCST 		 	 	 (Improving Approximate Matching Capabilities for Meta Map Transfer Applications) 
\bibitem[SIAM Symposium on Discrete Algorithms ()]{b0}\label{b0} 	 		\textit{SIAM Symposium on Discrete Algorithms},  				2004. p. .  	 
\bibitem[Daniel ()]{b11}\label{b11} 	 		‘speculative parallel pattern matching’.  		 			Daniel 		.  	 	 		\textit{ieee transactions on information forensics and security},  				2011. 6 p. .  	 
\bibitem[Charalampos]{b13}\label{b13} 	 		\textit{String matching on a multicore gpu using cuda", "parallel and distributed processing laboratory department of applied informatics, university of macedonia 156 egnatia str},  		 			S Charalampos 		.  		greece. 1591.  	 
\bibitem[Faro and Lecroq ()]{b5}\label{b5} 	 		‘The Exact Online String Matching Problem: a Review of the Most Recent Results’.  		 			S Faro 		,  		 			T Lecroq 		.  	 	 		\textit{ACM Computing Surveys}  		2013. 45  (2) .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
