\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={A Parallel Computational Approach for String Matching-A Novel Structure with Omega Model}, 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{A Parallel Computational Approach for String Matching-A Novel Structure with Omega Model} \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]{K Butchi Raju} \affil[1]{ GRIET AFF TO JNTUH} \renewcommand\Authands{ and } \date{\small \em Received: 7 December 2012 Accepted: 31 December 2012 Published: 15 January 2013} \maketitle \begin{abstract} In r e cent day?s parallel string matching problem catch the attention of so many researchers because of the importance in different applications like IRS, Genome sequence, data cleaning etc.,. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works have been published on the subject and research is still very active. In this paper we propose a omega parallel computing model for parallel string matching. The algorithm is designed to work on omega model pa rallel architecture where text is divided for parallel processing and special searching at division point is required for consistent and complete searching. This algorithm reduces the number of comparisons and parallelization improves the time efficiency. Experimental results show that, on a multi - processor system, the omega model implementation of the proposed parallel string matching algorithm can reduce string matching time. \end{abstract} \keywords{string matching; parallel string matching; computing model; omega mode l.} \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 tring matching has been extensively studied in the past 30 years. A string C of length n is a sequence of characters C1C2?Cn. Let ?=\{Y1, Y2, ? YN\} be a finite set of strings called patterns, and let I be an arbitrary string. The string matching problem is to identify and locate all substrings of I which are patterns in ?. It performs important tasks in many applications including information retrieval; library systems, artificial intelligence, pattern recognition, molecular biology, and text search and edit systems. The challenge is that for the string matching to be accurate, it needs to be able to search every byte of every input data streaming for a potential match from a large set of strings. So, normal software solutions are not enough, for this we need the hardware computing models {\ref [1]} {\ref [2]} {\ref [3]}\hyperref[b1]{[4]}\hyperref[b2]{[5]}\hyperref[b3]{[6]}\hyperref[b4]{[7]}.\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 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 algorit-hms, algorithmic models and finally conclude the study. \section[{II.}]{II.} \section[{Parallel Computing Models}]{Parallel Computing Models}\par Parallelism takes many forms and appears in many areas. It is exhibited at the CPU level when microinstructions are executed simultaneously. It is also present when an arithmetic or logic operation is realized by a circuit of small depth, as with carry-save addition. And it is present when multiple computers are connected together in a network. Parallelism can be available but go unused, either because an application was not designed to exploit parallelism or because a problem is inherently serial \hyperref[b5]{[8]}\hyperref[b6]{[9]}\hyperref[b7]{[10]}\hyperref[b8]{[11]}.\par A parallel computer is any computer that can perform more than one operation at time. By this dentition almost every computer is a parallel computer. For example, in the pursuit of speed, computer architects regularly perform multiple operations in each CPU cycle: they execute several microinstructions per cycle and overlap input and output operations (I/O) with arithmetic and logical operations. Architects also design parallel computers that are either several CPU and memory units attached to a common bus or a collection of computers connected together via a network. Clearly parallelism is common in computer science today \hyperref[b5]{[8]}\hyperref[b6]{[9]}\hyperref[b7]{[10]}\hyperref[b8]{[11]}.\par A parallel programming model is a concept that enables the expression of parallel programs which can be compiled and executed. The value of a programming model is usually judged on its generality: how well a range of different problems can be expressed and how well they execute on a range of different architectures. The implementation of a programming model can take several forms such as libraries invoked from traditional sequential languages, language extensions, or complete new execution models \hyperref[b5]{[8]}\hyperref[b6]{[9]}\hyperref[b7]{[10]}\hyperref[b8]{[11]}. \section[{III.}]{III.} \section[{Literature}]{Literature}\par Hundreds of articles, literally, have been published about string matching with computing models, exploring the multitude of theoretical and practical facets of this fascinating fundamental problem. For an n-character text T and an m-character pattern x, the classical algorithm by Knuth, Morris and Pratt takes O(n+m) time and uses O(m) auxiliary space to find all pattern occurrences in the text, namely, all text positions i, such that x = T[i ? i + m-1]. Many other algorithms have been published; some are faster on the average, or have other interesting benefits. This work categorizes the algorithms into some categories to emphasize the data structure that drives the matching. These categories are discussed here. a) Intrusion Detection Systems (Ids) {\ref Tuck et al.} proposed modifications to the wellknown Aho-Corasick string matching algorithm to reduce the amount of memory required to store known malicious strings and improve worst-case timing \hyperref[b9]{[12]}. They achieve results in both of these areas, while slightly degrading average-case performance. The proposed data storage methods for string matching are bitmap compression and path compression. Their experiments consider both an ASIC and a programmable router design. The ASIC design is tailored to only string matching, while the programmable design assumes an implementation that can be used for many different types of router applications. Experiment results show that the proposed compression optimizations resulted in a 50 times reduction in database size over the Aho-Corasick implementation.\par Dharmapurikar et al. \hyperref[b10]{[13]} proposed a hardware architecture based on parallel Bloom filters for network packet inspection. A Bloom filter is a space-efficient probabilistic data structure that is used to test whether or not an element is a member of a set. It stores a set of signatures compactly by computing multiple hash functions on each member of the set. The answer to querying a database of strings to check for the membership of a particular string can be "false positive", but never "false negative". False positive means a condition exists when in fact it does not. False negative means a condition does not exist when in fact it does. The computation time involved in performing the query is independent of the number of strings in the database, provided the memory used by the data structure scales linearly with the number of strings stored in it.\par J.Nandhini et al., {\ref [14]} provide a systematic virus detection software solution for network security for computer systems. Instead of placing entire matching patterns on a chip, proposed solution is based on an antivirus processor that works as much of the filtering information as possible onto a reference memory. The infrequently accessing off-reference data to make the matching mechanism scalable to large pattern sets. Dual port BITCAM processing program is used along with the Exact Matching Engine and Bloom Filter process. This Dual port BITCAM processes next to the exact matching engine and bloom filter process. This Dual port BITCAM process is placed exclusively for obtaining higher throughput.\par Performance Evaluation : From the above papers, it is possible to improve Snort's efficiency using distributed environment and testability of Snort has been enhanced. b) Dfa Based Approaches Dharmapurikar et al. presented a scheme \hyperref[b12]{[16]} that can process multiple characters per clock cycle and attain average throughput up to multi-gigabit with moderate memory consumption. But in the worst case they must access the relatively slow off-chip SRAMs frequently for exact string comparisons. Nan et al \hyperref[b13]{[17]}. Introduced a variable-stride method to deal with string matching ruleset without inciting the byte alignment problem. While enhancing the throughput, this method is sensitive to both ruleset and input string causing greatly reduced throughput in worst cases. Lu et al. \hyperref[b14]{[18]} introduced parallel DFAs with overlapping input windows to achieve the goal of processing multiple characters in each clock cycle. By slight modification to the straightforward representation of the transition rules, the complexity of each DFA is distinctively reduced. Brodie et al. \hyperref[b15]{[19]} increased the throughput of regex matching by expanding the alphabet set, resulting in an exponentially increased memory requirement in the worst case. A recent method D. Ficara et.al \hyperref[b16]{[20]} introduced the sampling techniques to accelerate regex matching, but not all kinds of regex are supported.\par WANG Xiaofei et. al \hyperref[b17]{[21]} proposed a parallel Length-based matching (LBM) architecture to increase the throughput without extra memory cost. The basic idea is to process multiple characters between some specific tags in parallel. For this they use multiple hash functions solution to reduce the possibility of false positive. The evaluation shows that parallel architecture can reduce nearly 55\% processing time with less memory consumption than the traditional DFA. According to proposed statistics, there are 99.41\% of the input stream has been filtered by architecture which means only 0.58\% (263.5M) need to be sent to StriD2FA to match instead of sending to the matching engine byte by byte. Besides the different type of traces, in this paper the other kind of trace that was collected from the World Wide Web should also be used to test the performance and stability.\par HyunJin Kim and Seung-Woo Lee \hyperref[b18]{[22]} proposed 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 \hyperref[b11]{[15]} suggest distributed environment in order to enhance the problems of Snort IDS, one of the problems is the efficiency problem. They achieved this goal by enhancing the Snort's string matching engine through using a LAN of computers, where each computer in the LAN matching a subset of the monitored attacks. Snort is an open source IDS which enable us to detect the previously known intrusion.\par storing state transitions can be shared. Therefore, the total memory requirement can be minimized by reducing the memory size for storing state transitions. In this, four large rule sets were extracted from Snort v2.8 rules. Several parameters were swept to find their optimal values. The maximum number of states S was 128 after considering the maximum length of Snort rules. When S was 128, the number of bits in a PMV P was either 16, 24, 32, or 40; when the number of states S was 256, P was either 32, 48, 64, or 80; the maximum number of entries in the LSB transition existence table, K, and the maximum number of shared state transitions, T, were double S, respectively. In Table {\ref 1}, the total memory requirements were shown by varying P. For the rule sets, the total memory requirements were minimized when S and P were 128 and 24, respectively.\par Performance Evolution : The memory requirements were not minimized by only increasing P over 24; therefore, there was a threshold point of P for minimizing memory requirements. In the evaluations in which S was 256, because the required K and P increased rapidly, the required number of string matchers was not decreased. Then, by fixing S and P as 128 and 24, K was varied to find the optimal value; K was either 192, 256, 320, or 384 because K should be greater than S. Each state can have one or more than one state transition. In these evaluations, T was fixed as 256. As a result, when K was 256, the total memory requirements were greatly reduced for all rule sets. This was mainly due to the limited number of state transitions toward noninitial states in each string matcher. With the optimal K of 256, T was varied, that is, T was either 128, 192, 256, or 320. The obtained optimal T was 256. In these evaluations, because state pointers can be shared in the transition table, the required T was small. Considering the optimal values of K and T, it is concluded that many state pointers can be shared in the transition table in the proposed string matcher. c) Parallel Processing Based Approaches Akhtar Rasool and Nilay Khare \hyperref[b19]{[23]} proposed an approach, which is designed to work on SIMD parallel architecture where text is divided for parallel processing and special searching at division point is required for consistent and complete searching. This algorithm reduces the number of comparisons and parallelization improves the time efficiency. This algorithm achieves a better result as compared to the multithreaded version of the algorithm where again by text dividing, the parallelization is achieved.\par cheng zhong and guo-liang chen \hyperref[b20]{[24]} presented a perfect hash function for processing string is constructed by applying the Chinese Remainder Theorem, and a fast string matching algorithm, which is suited to process the successive sequences like the network traffic data. The determinate match results and fast execution for the string matching algorithm are very important to the network intrusion detection systems. This paper constructs a perfect hash function for processing string by applying the Chinese Remainder Theorem, transforms uniquely a pattern of length m and each substring of text of length m into a pair of integer values respectively, and presents a fast string matching algorithm which is suited to process the successive sequences like the network traffic data. The presented algorithm not only obtains the determinate match results, but also holds a linear time complexity in the worst case. The experiment results for matching a sequence database in the network intrusion detection systems also shows that the presented algorithm is efficient.\par Panwei Cao and Suping Wu \hyperref[b21]{[25]} proposed a Parallel KMP algorithm based on MPI to get higher efficiency. The tradition pattern matching algorithm need backtrack and compare repeatedly, so that affects efficiency of algorithm. Knuth and others put forward KMP algorithm in order to promote efficiency of the pattern matching. They combine MPI and KMP algorithm using MPI's Multi process to parallel KMP algorithm. By reducing the time waiting for matching, improve the string matching efficiency. \section[{d) Aho Corasick Based Approaches}]{d) Aho Corasick Based Approaches}\par Wei Lin, Bin Liu \hyperref[b22]{[26]} presented a pipelined parallel approach for hardware implementation of Aho-Corasick (AC) algorithm for multiple strings matching called P2-AC. P2-AC organizes the transition rules in multiple stages and processes in pipeline manner, which significantly simplifies the DFA state transition graph into a character tree that only contains forwarding edges. In each stage, parallel SRAMs are used to store and access transition rules of DFA in memory. Transition rules can be efficiently stored and accessed in one cycle. The memory cost is less than 47\% of the best known AC-based methods. P2-AC supports incremental update and scales well with the increasing number of strings. By employing two-port SRAMs, the throughput of P2-AC is doubled with little control overhead.\par Chuanpeng Chen and Zhongping Qin \hyperref[b23]{[27]} proposed a high throughput configurable string matching architecture based on Aho-Corasick algorithm. The architecture can be realized by randomaccess memory (RAM) and basic logic elements instead of designing new dedicated chips. The bit-split technique is used to reduce the RAM size, and the byteparallel technique is used to boost the throughput of the architecture.\par By the particular design and comprehensive experiments with 100MHz RAM chips, one piece of the architecture can achieve a throughput of up to 1.6Gbps by 2-byte-parallel input, and we can further boost the throughput by using multiple parallel architectures.\par Hyun Jin Kim et.al \hyperref[b24]{[28]} proposed an Aho-Corasick algorithm based parallel string matching. In order to balance memory usage between homogeneous finite-state machine (FSM) tiles for each string matcher, an optimal set of bit position groups is determined. Target patterns are sorted by binary-reflected gray code (BRGC), which reduces bit transitions in patterns mapped onto a string matcher. In the evaluations of Snort rules, the proposed string matching outperforms the existing bit-split string matching.\par Alicherry et al. \hyperref[b25]{[29]} proposed an architecture consisting of TCAM and SRAM to implement the AC algorithm that utilizes the property of ternary matching of TCAM to achieve the matching of characters expressed in negation expressions. As a result, the space required for the transitions can be reduced. Pao et al. \hyperref[b26]{[30]} and W. Lin and B. Liu \hyperref[b27]{[31]} proposed pipeline architectures to implement the partial trie that only contains goto functions of the AC-trie so that it can reduce the space induced by failure functions. N. Hua et al. \hyperref[b28]{[32]} proposed another approach based on a block-oriented scheme instead of usually byte-oriented processing of patterns to reduce the memory usage. D. P. Scarpazza et al. \hyperref[b29]{[33]} proposed an optimized software approach for a multicore processor that splits keywords to fit in the local memories of the processing cores such that it can reach very high overall throughput. Y. Sugawara et al. \hyperref[b30]{[34]} proposed a string matching method called suffix based traversing (SBT) that is an extension of the AC-algorithm to process multiple input characters in parallel and to reduce the size of the lookup table. e) Finite Automata Based Approaches HyunJin Kim et al., \hyperref[b31]{[35]} proposes 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 subpatterns with a fixed length and 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. In order to identify each original long pattern being divided, a two stage sequential matching scheme is proposed for the successive matches with sub patterns. Experimental results show that total memory requirements decrease on average by 47.8\%-62.8\% for Snort and ClamAV rule sets, in comparison with several existing bit-split string matching methods.\par Yi-Hua E. Yang and Viktor K. Prasanna \hyperref[b32]{[36]} proposed a head-body finite automaton (HBFA) which implements SPM in two parts: a head DFA (H-DFA) and a body NFA (B-NFA). The H-DFA matches the dictionary up to a predefined prefix length in the same way as AC-DFA, but with a much smaller memory footprint. The B-NFA extends the matching to full dictionary lengths in a compact variable-stride branch data structure, accelerated by single-instruction multiple-data (SIMD) operations. A branch grafting mechanism is proposed to opportunistically advance the state of the H-DFA with the matching progress in the BNFA. Compared with a fully-populated AC-DFA, proposed HBFA prototype has < 1/5 construction time, requires < 1/20 run-time memory, and achieves 3x to 8x throughput when matching reallife large dictionaries against inputs with high match ratios. The throughput scales up 27x to over 34 Gbps on a 32-core Intel Manycore Testing Lab machine based on the Intel Xeon X7560 processors.\par Yi Tang et al., \hyperref[b33]{[37]} proposed a paper that extends the classic longest prefix principle from singlecharacter to multi-character string matching and proposes a multi-string matching acceleration scheme named Independent Parallel Compact Finite Automata (PC-FA). In this scheme, DFA is divided into k PC-FAs, each of which can process one character from the input stream, achieving a speedup up to k with reduced memory occupation. They introduce their observation against the prefix based automata algorithms and propose a new conception of inclusion-equivalence principle. Compared with traditional DFA approach and other improved work, PC-FA achieves a high speed-up with a lower memory cost.\par Performance Evolution : Experimental evaluations show that seven times of speedup can be practically achieved with a reduced memory size than up-to-date DFA-based compression approaches. They further propose a memory-efficient multi-string matching acceleration scheme named PC-FA Match Engine. f) Hardware Related Based Approaches KSMV Kumar et.al \hyperref[b34]{[38]} compared string matching on single processor with multi-processors in parallel environment on hypercube network. The total time taken by search pattern is going to reduces as the No. of processors increases in network. This application developed for text documents of size only MB. It may extend to any size i.e GB to TB also and any other format likes image and video files etc. There is lot of scope to develop new trends in this area by evolving modern methods and models for increasing search speed and accuracy. To fulfill here considered both KV-KMP and KV-boyer-moore string matching algorithms for pattern matching in large text data bases using three data sets and graph's drawn for different patterns. Actual test is conducted separately for single processor, two processors, three processors and four processors. Every time, while the test is conducted the program gives elapse time for each processor separately. Therefore the average time is calculated from output result based on the maximum time taken by the individual processor among the processors involved for the particular test. The results shows that the search time taken by single processor is more when compared with multiple processors. It is also observed that as the Yao Xin et al \hyperref[b35]{[39]} presented a hardware architecture for the BWT-based inexact sequence mapping algorithm using the Field Programmable Gate Array(FPGA). The proposed design can handle up to two errors, including mismatches and gaps. The original recursive algorithm implementation is dealt with using hierarchical tables, and is then parallelized to a large extension through a dual-base extension method. Extensive performance evaluations for the proposed architecture have been conducted using both Virtex6 and Virtex7 FPGAs. This design is considerably faster than a direct implementation. When compared with the popular software evaluation tool BWA, their architecture can achieve the same match quality tolerating up to two errors.\par Performance Evaluation : Their major contributions include: (1) improving the original inefficient recursive algorithm using hierarchical tables, (2)parallelizing the inexact search process and constructing a parallel architecture by using the consecutive dual-base extension method (3)evaluating the architectures with a different number of stack arrays and processing elements(PEs). Extensive evaluation experiments are performed using both simulation datasets and real datasets. With the same inexact search options with in two errors for their architecture and BWA software, the hardware architecture can realize the same search quality as BWA. Compared with different CPU platforms running the BWA aln process, their architecture is also capable of better performance in execution speed: the Virtex6 FPGA with 2PEs implemented exceeds all software platforms except for the multithread Xeon CPU; the Virtex7 FPGA implementing 6PEs, however, can reach up to 2 times faster than the Xeon CPU with 6 threads \hyperref[b35]{[39]}.\par Hoang Le, and Viktor K. Prasanna \hyperref[b36]{[40]} proposed an algorithm called "leaf-attaching" to preprocess a given dictionary without increasing the number of patterns. The resulting set of post processed patterns can be searched using any tree search data structure. It also present a scalable, high-throughput, Memory-efficient Architecture for large-scale String Matching (MASM) based on a pipelined binary search tree. The proposed algorithm and architecture achieve a memory efficiency of 0.56 (for the Rogets dictionary) and 1.32 (for the Snort dictionary). As a result, our design scales well to support larger dictionaries. Implementations on 45 nm ASIC and a state-of-the-art FPGA device (for latest Rogets and Snort dictionaries) show that proposed architecture achieves 24 and 3.2 Gbps, respectively. The MASM module can simply be duplicated to accept multiple characters per cycle, leading to scalable throughput with respect to the number of characters processed in each cycle. Dictionary update involves simply rewriting the content of the memory, which can be done quickly without reconfiguring the chip.\par TAN Jianlong et al., \hyperref[b37]{[41]} proposes a novel method to extract the partial strings from each pattern which maximizes search speed. More specifically, with this method they can compute all the corresponding searching time cost by theoretical derivation, and choose the location which yields an approximately minimal search time.. String matching plays a key role in web content monitoring systems. Suffix matching algorithms have good time efficiency, and thus are widely used. These algorithms require that all patterns in a set have the same length. When the patterns cannot satisfy this requirement, the leftmost m-characters, m being the length of the shortest pattern, are extracted to construct the data structure. They call such m-character strings as partial strings. However, a simple extraction from the left does not address the impact of partial string locations on search speed. They evaluate their method on two rule sets: Snort and ClamAV. Experiments show that in most cases, their method achieves the fastest searching speed in all possible locations of partial string extraction, and is about 5\%-20\% faster than the alternative methods.\par Prasad et.al., \hyperref[b38]{[42]} propose two new bit-parallel algorithms to solve the same problem. These new algorithms requires no verification and can handle patterns of length > w. These two techniques also use the same BPA of approximate matching and concatenation to form a single pattern from the set of r patterns. It compares the performance of new algorithms with existing algorithms and found that proposed algorithms MASM1 and MASM2 have better running time than the existing algorithms: MASM and BPA (running r times). Mosleh M. Abu-Alhaj et al., \hyperref[b39]{[43]} proposes a general platform for improving the existing Exact String-Matching algorithms executing time, called the PXSMAlg platform. The function of this platform is to parallelize the Exact String-Matching algorithms using the MPI model over the Master/Slaves paradigms. The PXSMAlg platform parallelization process is done by dividing the Text into several parts and working on these parts simultaneously. This improves the executing time of the Exact-String-Matching algorithms. They have simulated the PXSMAlg platform in order to show its competence, through applying the Quick Search algorithm on the PXSMAlg platform. The simulation result showed significant improvement in the Quick Search executing time, and therefore extreme competence in the PXSMAlg platform.\par PXSMAlg Platform Performance Analysis: They platform with the conventional method, that is, the sequential method. The simulation built is based on three main factors: executing time, speedup, and efficiency. Their simulation runs under the Aurora server, which consists of 14 nodes, with each node having 2 CPUs, a speed of 1300MHz and a 1GB memory; all nodes run the Linux OS. The results showed high performance of the PXSMAlg platform over the sequential methods g) Gpu's Based Approaches Benedikt Forchhammeret.al \hyperref[b40]{[44]} presented a complete duplicate detection workflow that utilizes the capabilities of modern graphics processing units (GPUs) to increase the efficiency of finding duplicates in very large datasets. Proposed solution covers several well-known algorithms for pair selection, attribute-wise similarity comparison, record-wise similarity aggregation, and clustering. Here redesigned these algorithms to run memory-efficiently and in parallel on the GPU. Proposed experiments demonstrate that the GPU-based workflow is able to outperform a CPUbased implementation on large, real-world datasets. For instance, the GPU-based algorithm deduplicates a dataset with 1.8m entities 10 times faster than a common CPU-based algorithm using comparably priced hardware.\par Antonino Tumeo et al., \hyperref[b41]{[45]} focus on the matching of unknown inputs streamed from a single source, typical of security applications and difficult to manage since the input cannot be preprocessed to obtain locality. They consider shared-memory architectures (Niagara 2, x86 multiprocessors and Cray XMT) and distributed memory architectures with homogeneous (InfiniBand cluster of x86 multicores) or heterogeneous processing elements (InfiniBand cluster of x86 multicores with NVIDIA Tesla C1060 GPUs).\par Performance Evolution: They have presented several software implementations of the Aho-Corasick pattern matching algorithm for high performance systems, and carefully analyzed their performance. They presented optimized designs for the various architectures, discussing several algorithmic strategies, for shared memory solutions, GPU-accelerated systems and distributed memory systems. They describe how each solution achieves the objectives of supporting large dictionaries, sustaining high performance, and enabling customization and flexibility using various data sets. They found that the absolute performance obtained on the Cray XMT is one of the highest reported in literature, at ? 28 Gbps (using 128 processors) for a software solution with very large dictionaries. This work compares several software-based implementations of the Aho-Corasick algorithm for high performance systems.\par Antonino Tumeo et.al \hyperref[b42]{[46]} presented several software implementations of the Aho-Corasick pattern matching algorithm for high performance systems, and carefully analyzed their performance. It considered the various tradeoffs in terms of peak performance, performance variability, and data set size. It presented optimized designs for the various architectures, discussing several algorithmic strategies, for sharedmemory solutions, GPU-accelerated systems, and distributed-memory systems. Finally from this paper found that the absolute performance obtained on the Cray XMT is one of the highest reported in the literature, at 28 Gbps (using 128 processors) for a software solution with very large dictionaries. Through multithreading and memory hashing the XMT is able to maintain stable performance across very different sets of dictionaries and input streams. A dual Niagara 2 obtains stable performance only in low and medium matching conditions, while a dual Xeon 5560 has more varied results, obtaining high peak rates for light matching conditions, but progressively reducing its performance as the number of matches' increases. \section[{h) Ram Based Approaches}]{h) Ram Based Approaches}\par Vinod.O et.al \hyperref[b43]{[47]} proposes an alternative algorithm using a Hash Function which uses a SRAM that creates fingerprints of the packet payload which are then compared with the patterns signatures. The proposed hash based system consumes around 0.56 times or 56 percent less memory than the memory consumed by the RTCAM method. It can also be observed from the results that as the TCAM width doubles the initial width the memory consumption increases around 1000kb the initial memory consumption value in RTCAM method. But in the case of hash based method as the block size is doubled the memory consumption increases by a small value around 200kb only from the initial memory consumption value. Hence the proposed hash based method is efficient than the RTCAM method in terms of memory consumption.\par Oren Ben-Kiki et al., \hyperref[b44]{[48]} proposed macro-level algorithm only uses the standard AC instructions of the word-RAM model (i.e. no integer multiplication) plus two specialized micro-level AC 0 word-size packed-string instructions. The main word-size string matching instruction wssm is available in contemporary commodity processors. The other word-size maximumsuffix instruction wslm is only required during the pattern pre-processing.\par Performance avolution: They demonstrated how to employ word-size string matching instructions to design optimal packed string matching algorithms in the word-RAM, which are fast both in theory and in practice They also consider the complexity of the packed string matching problem in the classical word-RAM model in the absence of the specialized micro-level instructions wssm and wslm.They propose micro-level algorithms for the theoretically efficient emulation using parallel C algorithms techniques to emulate wssm and using the Four-Russians technique to emulate wslm. Surprisingly, bit-parallel emulation of wssm also leads to a new simplified parallel random access machine string matching algorithm. As a byproduct to facilitate their results they develop a new algorithm for finding the leftmost (most significant) 1 bit in consecutive nonoverlapping blocks of uniform size inside a word. i) Approaches For Genome Sequences More approaches have been developed for the k differences problem in fields including molecular biology. Some of them are briefly mentioned in this part. Cheng and Fu \hyperref[b45]{[49]} proposed VLSI architecture of two dimensional arrangements of n*m processing elements. P-NAC (Princeton Nucleic Acid Comparator) \hyperref[b46]{[50]} was built using linear systolic array architecture for comparing DNA sequences.\par Similarly, Sastry et al \hyperref[b47]{[51]} presented a VLSI chip for computing similarity between two strings. Two generations of the Splash processors, which are based on systolic arrays of FPGAs (field-programmable gate arrays) have been designed \hyperref[b48]{[52]}. As Foster and Kung \hyperref[b49]{[53]} mentioned, the good algorithms for VLSI implementation are not necessarily those requiring minimal computation. Computation is cheap in VLSI and the communication determines the performance. This matter is also applicable to the dataflow environment. As used in most high performance software string matching algorithms, trial of skipping operations will degrade the overall performance of the dataflow algorithm. Thus we start from the naïve algorithm which requires n-m+1 attempts and each attempt takes m comparisons.\par Carla Correa Tavares dos Reis and Oswaldo Cruz \hyperref[b50]{[54]} presented the development of algorithms for approximate string matching using parallel methods. It intends to do the maximum of molecular sequences comparisons per unity of time. The parallel program implementation has carried out in C on an available twenty processing nodes clustering architecture using a model of parallel programming systems, the MPI (Message-Passing Interface), which is as library of subroutines. In this paper also concerned with reporting the speedup and efficiency measures. More precisely, present a parallel algorithm for approximate sequence matching, showing its implementation and reporting its measures in comparison to its sequential version. It use one of the possible approaches to reduce the time spent on comparisons of molecular database sequences by distributing the data among processors, which achieves a linear speedup (time) and requires constant space memory per processor. It also compares between the serial processing and the parallel processing (under the operation conditions offered by MPI ambient), the parallel version always gave the best results (execution and data distribution times).\par Muhammad Zubair et al., {\ref [55]} propose a new concept to solve the problem of exact string matching by scanning text string for the rightmost character of the pattern in preprocessing phase. In matching phase TSPRC (Test Scanning for Pattern Rightmost Character) compares the pattern with text window from both directions simultaneously. They proposed a new algorithm TSPRC,in addition to proposed algorithm Naive, Not So Naive, quick Search, Boyer Moor Bad Character and Berry Ravindran algorithms are experimented with TSPRC. In the experiment they took a text string T of the size of sixty thousand characters and pattern P of lengths \{6, 12, 18, 24, 30, 36, 42, 48, 54, 60\}. Text String is consisted of the four characters L= \{A, C, G, T\} these are the characters occurred in DNA pattern. Pattern is also of L=\{A, C, G, and T\}. Several experiments have been conducted and the obtained results are compared with Naive, Not So Naive, Quick Search and Berry Ravndrn algorithms. Comparison made on two bases; total number of characters compared by each algorithm and the number attempts taken by each algorithm for finding all possible occurrence of the pattern in the text.\par Performance Evolution : Comparison of proposed algorithm is made with existing algorithms on the bases of the number of characters compared and the attempts made by experimented algorithms to complete the task. In preprocessing phase of TSPRC; rightmost character of pattern is searched in the text string. Index of the character in the text string is used to calculate the shift's length and align the pattern with next text window. The analysis and the experimental results illustrate that the TSPRC algorithm is better than the number of existing algorithms.\par Tomohiro I et al., {\ref [56]} presented a linear-time algorithm to solve the palindrome pattern matching problem. The first algorithm is a Morris-Pratt type algorithm, and the second one is a suffix-tree type algorithm. The palindrome pattern matching problem is to compute all positions i of t such that Pals(p) = Pals(t[i : i + m ? 1]), given a text t of length n and a pattern p of length m. Palindromes in strings have widely been studied both in theoretical and practical contexts, such as in word combinatorics and in bioinformatics In practical applications such as DNA and RNA sequence analysis, it is desired to cope with gapped palindromes which have a space between the left and right arms of the palindromes. \section[{IV. Scattered Computing and Scattered Algorithms}]{IV. Scattered Computing and Scattered Algorithms}\par The new technologies of networking and the dramatic evolution of the internet and intranet impacts the way that we use computers and changes the way we create applications for them. Distributed applications are becoming the natural way to build software. "Distributed computing" is all about designing and building applications as a set of processes that are distributed across a network of machines and work together as an ensemble to solve a common problem \hyperref[b5]{[8]}\hyperref[b6]{[9]}\hyperref[b7]{[10]}\hyperref[b8]{[11]}. Distributed algorithms are algorithms designed to run on a distributed system; where many processes cooperate by solving parts of a given problem in parallel. For this purpose, the processes have to exchange data and synchronize their actions. In contrast to so called parallel algorithms, communication and synchronization is solely done by message passingthere are no shared variables-and usually the processes do not even have access to a common clock. Since message transmission time cannot be ignored, no process has immediate access to the global state. Hence, control decisions must be made on a partial and often outdated view of the global state which is assembled from information gathered gradually from other processes. Distributing computing requires a tool by which the distributed machines can communicate. Many tools are available such as Remote Method Invocation (RMI), CORBA and Java Space. Each tool has its own specifications; the application designer chooses the appropriate one for his application requirement \hyperref[b5]{[8]}\hyperref[b6]{[9]}\hyperref[b7]{[10]}\hyperref[b8]{[11]}.\par In this, paper we examine a number of explicitly parallel models of computation for string matching, including shared and distributed memory models proposed by different researchers and proposed a computing model with omega architecture. \section[{V.}]{V.}\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 Fig2.\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 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 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. 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. Here we have to implement the proposed system with JAVA 1.7 multi threading; initially we have to implement the proposed algorithm with threading on Multicore processor. Here we discuss some of them. Computing model consists of the good suffix and bad-character shift function. The bad character shift means to shift the pattern so that the text character of the mismatch is aligned to the last occurrence of that character in the initial part of the pattern (pattern minus last pattern character), if there is such an occurrence, or one position before the pattern if the mismatched character doesn't appear in the initial part of the pattern at all.\par The other shift, the good suffix shift, aligns the matched part of the text, m, with the rightmost occurrence of that character sequence in the pattern that is preceded by a different character (including none, if the matched suffix is also a prefix of the pattern) than the matched suffix m of the pattern.\par 6. Each processor stores the MATCH results and RETURNS to the main program. 7. The main program collect the return results from all the processors and summing them 8. STOP. \section[{c) Claims}]{c) Claims}\par 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 The {\ref Fig 12 shows (Graph)} Execution time vs File size on parallel search with intel i3 processor using Boyer Moore, Brute force, KMP and proposed Algorithm. This graph shows the performance difference between Boyer Moore, Knuth Morris Pratt and Brute force algorithms. From the graph clearly observe that proposed is better compared to other approaches, as well as this parallel approach is much better compared to sequential approaches.\par The {\ref Fig 13 shows (Graph)} Execution time vs File size on sequential search with intel i5 processor using Boyer Moore, Brute force, KMP and proposed Algorithm. This graph shows the performance difference between Boyer Moore, Knuth Morris Pratt and Brute force algorithms. From the graph clearly observe that proposed is better compared to other approaches. File size on parallel search with intel i5 processor using Boyer Moore, Brute force, KMP and proposed Algorithm. This graph shows the performance difference between Boyer Moore, Knuth Morris Pratt and Brute force algorithms. From the graph clearly observe that proposed is better compared to other approaches, as well as this parallel approach is much better compared to sequential approaches. \section[{Conclusions}]{Conclusions}\par In this study, we widely investigate the problem of parallel string matching in the context of Parallel Computing with omega model. This Parallelization greatly improves the matching efficiency if the text size is very large and a sufficient numbers of processors are available. The most important characteristic of the proposed algorithm is that reduces the number of comparisons by making better use of next bit characters. Further parallelization of proposed algorithm provides parallel computing of pattern searching on the text in omega architecture. Experimental shows that proposed algorithm much more better than other approaches both sequential and parallel. \begin{figure}[htbp] \noindent\textbf{}\includegraphics[]{image-2.png} \caption{\label{fig_0}C}\end{figure} \begin{figure}[htbp] \noindent\textbf{}\includegraphics[]{image-3.png} \caption{\label{fig_1}C}\end{figure} \footnote{© 2013 Global Journals Inc. (US)} \backmatter \begin{bibitemlist}{1} \bibitem[Cao and Wu ()]{b21}\label{b21} \textit{}, Panwei Cao , Suping Wu . \textit{Parallel Research on KMP Algorithm} 2011. IEEE. p. . \bibitem[Valiant (1990)]{b5}\label{b5} ‘A bridging model for parallel computation’. Leslie G Valiant . \textit{Commun. ACM} August, 1990. 33 (8) p. . \bibitem[Cheng Zhong and Chen ()]{b20}\label{b20} ‘a fast determinate string matching algorithm for the network intrusion detection systems’. Guo-Liang Cheng Zhong , Chen . \textit{Proceedings of the Sixth International Conference on Machine Learning and Cybernetics}, (the Sixth International Conference on Machine Learning and CyberneticsHong Kong) 2007. p. . \bibitem[Kim and Lee ()]{b18}\label{b18} ‘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[Le and Prasanna ()]{b36}\label{b36} ‘A Memory-Efficient and Modular Approach for Large-Scale String Pattern Matching’. Hoang Le , Viktor K Prasanna . \textit{IEEE Transactions on Computers} 2013. 62 (5) p. . \bibitem[Kim (2010)]{b31}\label{b31} ‘A Memory-Efficient Bit-Split Parallel String Matching using Pattern Dividing for Intrusion Detection Systems’. Hyunjin Kim . \textit{IEEE Transactions On Parallel And Distributed Systems, Third Draft}, September 2010. 2011. p. . \bibitem[Kim et al. ()]{b24}\label{b24} ‘A Memory-Efficient Parallel String Matching for Intrusion Detection Systems’. Hyunjin Kim , Hyejeong Hong , Hong-Sik Kim , Sungho Kang . \textit{IEEE COMMUNICATIONS LETTERS} 2009. 13 (12) p. . \bibitem[Pao et al. ()]{b26}\label{b26} ‘A memory-efficient pipelined implementation of the Aho-Corasick string-matching algorithm’. D Pao , W Lin , B Liu . \textit{ACM Trans. on Archit. Code Optim} 2010. 7 p. . \bibitem[Lu et al. ()]{b14}\label{b14} ‘A memoryefficient parallel string matching architecture for high-speed intrusion detection’. H Lu , K Zheng , B Liu , X Zhang , Y Liu . \textit{IEEE JSAC} 2006. 24 (10) p. . \bibitem[Brodie et al. ()]{b15}\label{b15} ‘A scalable architecture for high-througshput regularexpression pattern matching’. B C Brodie , D E Taylor , R K Cytron . \textit{Proc. Of ACM/IEEE International Symposium on Computer Architecture (ISCA)}, (Of ACM/IEEE International Symposium on Computer Architecture (ISCA)Boston, MA, USA) 2006. p. . \bibitem[Dharmapurikar et al. ()]{b10}\label{b10} ‘Advance virus detection using combined techniques of pattern matching and dynamic instruction sequences’. S Dharmapurikar , P Krishnamurthy , T S Sproull , J W Lockwood . \textit{International Journal of Communication and Computer Technologies} 14. J.Nandhini, Dr.M. Nithya, Dr.S.Prabhakaran (ed.) 2004. 24 (1) p. 2013. (IEEE Micro) \bibitem[Tumeo et al. ()]{b42}\label{b42} ‘Aho-Corasick String Matching on Shared and Distributed-Memory Parallel Architectures’. Antonino Tumeo , Oreste Villa , Daniel G Chavarr?´a-Miranda . \textit{IEEE Transactions on Parallel and Distributed Systems} 2012. 23 (3) p. . \bibitem[Tumeo ()]{b41}\label{b41} ‘Aho-Corasick String Matching on Shared and Sistributed Memory Parallel Architectures’. Antonino Tumeo , G . \textit{IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS} 2011. IEEE. p. . \bibitem[Mosleh and Abu-Alhaj ()]{b39}\label{b39} ‘An Innovative Platform To Improve The Performance Of Exact-String Matching ALGORITHMS’. M Mosleh , Abu-Alhaj . \textit{IJCSIS) International Journal of Computer Science and Information Security} 2010. 2010. 7 (1) p. . \bibitem[Correa Tavares Dos Reis and Cruz ()]{b50}\label{b50} \textit{Approximate String Matching Algorithm Using Parallel Methods for Molecular Sequence Camparisons}, Carla Correa Tavares Dos Reis , Oswaldo Cruz . 2005. IEEE. p. . \bibitem[Chuanpeng Chen and Zhongping Qin A Bit-split Byte-parallel String Matching Architecture ()]{b23}\label{b23} \textit{Chuanpeng Chen and Zhongping Qin A Bit-split Byte-parallel String Matching Architecture}, 2009. IEEE. p. . \bibitem[Foster ()]{b6}\label{b6} \textit{Designing and Building Paral lel Programs}, I Foster . 1996. Addison Wesley. \bibitem[Tuck et al. (2004)]{b9}\label{b9} ‘Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection’. N Tuck , T Sherwood , B Calder , G Varghese . \textit{Proceedings of IEEE Infocom}, (IEEE InfocomHong Kong) March 2004. \bibitem[Forchhammer et al. ()]{b40}\label{b40} \textit{Duplicate Detection on GPUs}, Benedikt Forchhammer , Thorsten Papenbrock , Thomas Stening , Sven Viehmeier , Uwe Draisbach , Felix Naumann . 2013. p. . \bibitem[Prasad et al. (2011)]{b38}\label{b38} ‘Efficient bitparallel multi-patterns approximate string matching algorithms’. Rajesh Prasad , Anuj Kumar Sharma , Alok Singh , Suneeta Agarwal1 , Sanjay Misra . \textit{Scientific Research and Essays} 18 February, 2011. 6 (4) p. . \bibitem[Scarpazza et al. ()]{b29}\label{b29} \textit{Exact multipattern string matching on the cell/b.e. processor, ACM CF}, D P Scarpazza , O Villa , F Petrini . 2008. \bibitem[Dharmapurikar and Lockwood ()]{b12}\label{b12} ‘Fast and scalable pattern matching for network intrusion detection system’. S Dharmapurikar , J W Lockwood . \textit{IEEE JSAC} 2006. 24 (10) p. . \bibitem[Mukhopadhyay (1979)]{b47}\label{b47} ‘Hardware Algorithms for Nonnumeric Computation’. Amar Mukhopadhyay . \textit{IEEE trans. on Computers} June 1979. (6) p. . \bibitem[Vinod and Sagar ()]{b43}\label{b43} ‘Hash-Based String Matching Algorithm For Network Intrusion Prevention systems (NIPS)’. B O M Vinod , Sagar . \textit{International Journal of Advanced Computer Theory and Engineering} 2013. (2) p. . \bibitem[Alicherry et al. ()]{b25}\label{b25} \textit{High speed pattern matching for network IDS/IPS, IEEE ICNP}, M Alicherry , M Muthuprasanna , V Kumar . 2006. p. . \bibitem[Simon and Inayatullah ()]{b1}\label{b1} ‘Improving Approximate Matching Capabilities for Meta Map Transfer Applications’. Y Simon , M Inayatullah . \textit{of Symposium on Principles and Practice of Programming in Java}, 2004. p. . \bibitem[Tang ()]{b33}\label{b33} \textit{Independent Parallel Compact Finite Automatons for Accelerating Multi-String Matching}, Yi Tang . 2010. (IEEE Globecom 2010 proceedings) \bibitem[Sugawara et al. ()]{b30}\label{b30} ‘Over 10Gbps string matching mechanism for multi-stream packet scanning systems’. Y Sugawara , M Inaba , K Hiraki . \textit{Field Programmable Logic and Application} 2004. 3203 p. . \bibitem[Ksmv Kumar et al. ()]{b34}\label{b34} ‘Overlapped Text Partition Algorithm for Pattern Matching on Hypercube Networked Model’. S Ksmv Kumar , A Viswanadha Raju , Govardhan . \textit{GJCST}, 2013. p. . \bibitem[Daniel and Lopresti (1987)]{b46}\label{b46} ‘P-NAC : A Systolic Array for Comparing Nucleic Acid Sequences’. P Daniel , Lopresti . \textit{Computer} July 1987. p. . \bibitem[Someswararao et al. ()]{b2}\label{b2} \textit{Parallel Algorithms for String Matching Problem based on Butterfly Model}, Chinta Someswararao , Butchiraju , Viswanadharaju . July -Sept, ISSN 2229-4333, 2012. 3 p. . IJCST \bibitem[Xin et al. ()]{b35}\label{b35} ‘Parallel architecture for DNA sequence inexact matching with Burrows-Wheeler Transform’. Yao Xin , Benben Liu , Biao Min , . Y Willx , Li , C C Ray , Anthony S Cheung , Ting Fong , Fung Chan . \textit{Microelectronics Journal} 2013. Elsevier. p. . \bibitem[Wang Xiaofei et al. ()]{b17}\label{b17} ‘Parallel Length-based Matching Architecture for High Throughput Multi-Pattern Matching’. Wang Xiaofei , Hu Chengchen , Yi , Ting , Liu Wu Chunming , Bin , Wang Xiaojun . \textit{Chinese Journal of Electronics} 2012. 21 (3) p. . \bibitem[Foster and Tuecke (1991)]{b7}\label{b7} \textit{Parallel Programming with PCN}, I Foster , S Tuecke . ANL-91/32. December 1991. Argonne. Argonne National Laboratory (Technical Report) \bibitem[Raju ()]{b4}\label{b4} ‘parallel string matching algorithm using grid", "international journal of distributed and parallel systems’. S Raju . \textit{ijdps} 2012. 3 (3) . \bibitem[Rasool and Khare ()]{b19}\label{b19} ‘Parallelization of KMP String Matching Algorithm on Different SIMD architectures-Multi-Core and GPGPU’. Akhtar Rasool , Nilay Khare . \textit{International Journal of Computer Applications} 2012. p. . \bibitem[Lin and Liu ()]{b22}\label{b22} ‘Pipelined Parallel AC-based Approach for Multi-String Matching’. Wei Lin , Bin Liu . \textit{14th IEEE International Conference on Parallel and Distributed Systems}, 2008. p. . \bibitem[Lin and Liu ()]{b27}\label{b27} ‘Pipelined parallel AC-based approach for multi-string matching’. W Lin , B Liu . \textit{IEEE ICPADS} 2008. p. . \bibitem[Butchiraju et al. ()]{b0}\label{b0} ‘Recent Advancement is Parallel Algorithms for String matching on computing models -A survey and experimental results’. Butchiraju , ; Viswanadharaju , K Someswararao , Butchiraju , ; Viswanadharaju , K Someswararao , Butchiraju , Viswanadharaju . \textit{IEEE conference on Application of Information and Communication Technologies}, 2011. 2011. 2012. Springer. ISBN p. . (IJAC) \bibitem[Someswararao et al. ()]{b3}\label{b3} ‘Recent Advancement is String matching algorithms-A survey and experimental results’. Chinta Someswararao , Butchiraju , Viswanadharaju . \textit{IJCIS} 2013. 6 (3) p. . \bibitem[Fawcett (1995)]{b48}\label{b48} ‘Reconfiguring a Computing Pattern’. Bradly Fawcett . \textit{Electronic Engineering Times} April. 1995. p. 64. \bibitem[Yi-Hua et al. ()]{b32}\label{b32} ‘Robust and Scalable String Pattern Matching for Deep Packet Inspection on Multi-core Processors’. E Yi-Hua , Yang , K Viktor , Prasanna . \textit{IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS} 2012. p. . \bibitem[Ficara et al. ()]{b16}\label{b16} ‘Sampling techniques to accelerate pattern matching in network intrusion detection systems’. D Ficara , G Antichi , A D Pietro , S Giordano , G Procissi , F Vitucci . \textit{Proc. of IEEE ICC}, (of IEEE ICCCape Town, South Africa) 2010. p. . \bibitem[Tan Jianlong ()]{b37}\label{b37} ‘Speeding up Pattern Matching by Optimal Partial String Extraction’. Tan Jianlong . \textit{the first international workshop on security in computers, networking and communications}, 2011. IEEE. p. . \bibitem[Safaa and Al-Mamory]{b11}\label{b11} \textit{String Matching Enhancement for Snort IDS}, O Safaa , Al-Mamory . p. . \bibitem[Darlinton et al. ()]{b8}\label{b8} \textit{Structured Parallel Programming", In Programming Models for Massively Parallel Computers}, J Darlinton , M Ghanem , H W To . 1993. 1993. IEEE Computer Society Press. \bibitem[Foster and Kung (1980)]{b49}\label{b49} ‘The Design of Special-Purpose VLSI Chips’. M J Foster , H T Kung . \textit{Computer} Jan. 1980. p. . \bibitem[Ben-Kiki et al. (2013)]{b44}\label{b44} \textit{Towards Optimal Packed String Matching}, Oren Ben-Kiki , Philip Bille , Dany Breslauer , Leszek Gasieniec , Roberto Grossi , Oren Weimann . July 10, 2013. p. . \bibitem[Hua et al. ()]{b28}\label{b28} ‘Variablestride multi-pattern matching for scalable deep packet inspection’. N Hua , H Song , T V Lakshman . \textit{IEEE INFOCOM}, 2009. p. . \bibitem[Hua et al. ()]{b13}\label{b13} ‘Variablestride multipattern matching for scalable deep packet inspection’. N Hua , H Song , T V Lakshman . \textit{Proc. of INFOCOM}, (of INFOCOMRio de Janeiro, Brazil) 2009. p. . \bibitem[Cheng and Fu ()]{b45}\label{b45} ‘VLSI Architecture for String Matching and Pattern Matching’. H D Cheng , K S Fu . \textit{Pattern Recognition} 1987. 20 p. . \end{bibitemlist} \end{document}