pattern matching

Pattern Search in Grid

Problem Statement Given a huge grid G with M rows and N columns and a pattern P with m rows and n columns. The task at hand is to perform a pattern search in grid, and print YES if the pattern grid P exists in the grid G otherwise print NO [caption id="attachment_3611" align="aligncenter" width="960"] Pattern Search in Grid[/caption] Its a simple string search but requires special attention to the boundary cases. Here is a list of them We only need to test the grid G for M-m rows, because anything below row R-r  cannot accommodate the pattern of size r. We only need to test the gr...
Read More

Pattern Finding – KMP Algorithm

Introduction Now that you are fully equipped with the Boyer Moore Algorithm and have a notion of Pattern Finding. I would suggest you to get deeper into pattern finding. You can read about the benefits of pattern finding in my previous post about Boyer Moore. This post will try to make you familiar with all the thought processes which you can use to exploit the known properties of texts and patterns using KMP Algorithm. However, Boyer Moore seems to be slightly intuitive, this one is a real geeky way of finding patterns. Knuth Morris Pratt Yes! this is what KMP stands for, you can learn ...
Read More

Pattern Finding – Boyer Moore

Introduction String matching problems are important part of many Programming Contests and also find applications in real world problems. Imagine you are asked to implement a text editor. What are few of the most common operations in a text editor? Copy and Paste. Search and Replace. The performance of your text editor will completely depend on how efficiently it can search and/or replace patterns in a huge text. Basics of Pattern Finding In a given pattern matching problem, we have two strings one is called the text T and the other is called the pattern P. The task is to find th...
Read More