regex - Algorithm for 2 Pattern String Matching -


I need an algorithm code to match two pattern prefix / suffix for the longest time, whose time complexity is O (n + M1 + m2), where n is the length of string and m1, m2 is the length of pattern 1 and pattern 2 respectively. Example: If the string is "obtoto" and the pattern is 1 "bana" and Patton 2 is "SIESTA", then the answer is "nickname" of the string, in which the prefix of Bana and the suffix Ti of SIESTA are included. Results from Google: "Rabin-Carp String Search Algorithm", "Noth-Morris-Prat Algorithm" and "Bauer-Moore String Search Algorithm".

I am able to understand all of the above 3 algorithms, but the problem is that they are unable to expand to all the "single pattern prefix / suffix matching" to match them in two pattern prefix / suffix.

A sample algorithm or a link to search would be very useful for me in developing the program.

Knuth - Morris - Protea can be modified directly for yield, each in the greenstack string For the position, the length of the long prefix of the needle string with the match ending at that place. Use KMP to calculate this information for the straight and reverse (pat 2) of Pat 1 in the string, then repeat the string in search of the maximum length of each prefix / suffix. Example with string = "Obantao" and Pat 1 = "Bana" and Pat 2 = "SESESTA": 

  "Bana" = Pat 1 ^ in Straight Obaneta ^ ^ ^ | | | | | | | | | | | | | | | 0 ("") | | | | | | 0 ("") | | | | | 0 ("") | | | | 3 ("ban"). | | 2 ("BA"). | 1 ("B"). 0 ("") 0 ("") "ATSIS" = Reverse (Pat 2) reverse (string) O ATNAB He ^ ^ ^ ^ ^ ^ | | | | | | | | | | | | | | | 0 ("") | | | | | | 0 ("") | | | | | 1 ("A"). | | | 0 ("") | | | 2 ("AT"). | 1 ("A"). 0 ("") 0 ("")

Reverse by second array and amount. 

  0 0 2 3 0 0 0 + 0 0 1 0 2 1 0 0 ----------------- 0 0 2 2 5 1 0 | ^ | Maximum (argument = "bain" ++ reverse ("at")

Comments

Post a Comment

Popular posts from this blog

ios - How do I use CFArrayRef in Swift? -

I am using Objective-class in my Swift Project through a bridging header. The method signature looks like this: - Some cement (some type) some parameters; I started by getting an example of class, calling method, and storing the value: var myInstance = MyClassWithThatMethod (); Var cfArr = myInstance.someMethod (some value); Then try to get the value in the array: var valueInArrayThatIWant = CFArrayGetValueAtIndex (cfArr, 0); However, I get the error unmanaged & lt; Cfarray & gt; Not like 'CFArray' . Unmanaged & lt; Cfarray & gt; also means? I looked, but I do not need to change the array in a fast array (though it would be good). I need to be able to get value from the array. I also tried CFArray method to pass in a function: func doSomeStuffOnArray (myArray: NSArray) {} Although I get the same error when using: doSomeStuffOnArray (cfArr); // unmanaged & lt; CFArray & gt; I am using CFArray because I want to sto...
Read more

eclipse plugin - Run java code error: Workspace is closed -

To create an automated project, I created a plug-in project with the following dependencies: Org.eclipse.core.resources org.eclipse.equinox.registry org.eclipse.core.runtime and the following The Java class is located in the src folder: Package Examiner; Import org.eclipse.core.resources.IProject; Import org.eclipse.core.resources.IWorkspaceRoot; Import org.eclipse.core.resources.ResourcesPlugin; Import org.eclipse.core.runtime.CoreException; Import org.eclipse.core.runtime.IProgressMonitor; Import org.eclipse.core.runtime.NullProgressMonitor; Public class tes {public static zero main (string [] args) {// TODO auto generated method stub IProgressMonitor progress monitor = new NullProgressMonitor (); IWorkspaceRoot root = ResourcesPlugin.getWorkspace (). GetRoot (); Ipoject project = root.jetproject ("desired projectname"); Try {Project.create (progress monitor); Project.open (progressMonitor); } Grip (CoreException E) {// TODO Auto generated blocking block e....
Read more

c - Error on building source code in VC 6 -

When I create my project in VC6, the BScMKE reports the following error Linking .. Creating Library ... .. / ... / PB / Bean / Debub / ICEERP.Lib and Object ........ P.B. / Bean / DBube / ICREPlay.APP Browse information file ... BSMMK: ​​error can not be read from BK 1505: file '../../PB/bin/TmpOut/ICReplay/Debug/ICReplay_PB.bsc' Error executing bscmake.exe Can someone help me? 2 Reason for reference from: "ICReplay_PB .bsc "file will be corrupted The trunk of the file will be happening with the compiler running out of disk space or is being interrupted when creating .sbr file I think this answer will help you!
Read more