数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


DSA - Pattern Searching

What is Pattern Searching?

The pattern searching/matching algorithm is a technique that is used to locate or find a specific pattern or substring within given text. Its basic idea is to find all the occurrences of a particular pattern in the specified data structure. For instance, given an array of numbers [1, 2, 3, 4, 5, 6, 3, 4, 9] and we need to find all the occurrences of the pattern [3, 4] in the array. The answer would be index number 2 and 6.

Pattern Matching

How pattern searching algorithm works?

There are multiple pattern searching algorithms that works in different ways. The main goal to design these type of algorithms is to reduce the time complexity. The traditional approach may take lots of time to complete the pattern searching task for a longer text.

If we are saying traditional approach, we are actually referring to brute force approach for solving pattern searching problems. Let's see how it works −

  • Slide the pattern over the text.

  • Compare each character one by one.

  • If all the characters match, we have found a match.

  • If not, move the pattern one position to the right and repeat the process until we reach the end of the text or find a match.

Pattern Solving

Remember, brute force is the simplest way to solve string matching or searching, but it is also the slowest and most inefficient. The time complexity of this algorithm is O(nm), where 'n' is the length of the text and 'm' is the length of the pattern. This means that in the worst case, we have to compare every character of the text with every character of the pattern, which can be very slow if n and m are large. There are other algorithms also that are mentioned in the next section.

Example

In this example, we will practically demonstrates the brute force approach to solve a pattern matching problem in various programming languages.

#include <stdio.h>
#include <string.h>
// method to find match
void findMatch(char *orgText, char *pattern) {
   int n = strlen(orgText);
   int m = strlen(pattern);
   // comparing the text and pattern one by one
   for (int i = 0; i <= n-m; i++) {
      int j = 0;
      while (j < m && orgText[i+j] == pattern[j]) {
         j++;
      }
      // print result if found
      if (j == m) {
         printf("Oohhoo! Match found at index: %d
", i);
         return; 
      }
   }
   // if not found
   printf("Oopps! No match found
");
}
int main() {
   // Original Text
   char orgText[] = "Tutorials Point";
   // pattern to be matched
   char pattern[] = "Point";
   // method calling
   findMatch(orgText, pattern); 
   return 0;
}
#include <iostream>
#include <string>
using namespace std;
// method to find match
void findMatch(string orgText, string pattern) {
   int n = orgText.length();
   int m = pattern.length();
   // comparing the text and pattern one by one
   for (int i = 0; i <= n-m; i++) {
      int j = 0;
      while (j < m && orgText[i+j] == pattern[j]) {
         j++;
      }
      // print result if found
      if (j == m) {
         cout << "Oohhoo! Match found at index: " << i << endl;
         return; 
      }
   }
   // if not found
   cout << "Oopps! No match found" << endl;
}
int main() {
   // Original Text
   string orgText = "Tutorials Point";
   // pattern to be matched
   string pattern = "Point";
   // method calling
   findMatch(orgText, pattern); 
   return 0;
}
public class PattrnMatch {
   public static void main(String[] args) {
      // Original Text
      String orgText = "Tutorials Point";
      // pattern to be matched
      String pattern = "Point";
      // method calling
      findMatch(orgText, pattern); 
   }
   // method to find match
   public static void findMatch(String orgText, String pattern) {
      int n = orgText.length();
      int m = pattern.length();
      // comparing the text and pattern one by one
      for (int i = 0; i <= n-m; i++) {
         int j = 0;
         while (j < m && orgText.charAt(i+j) == pattern.charAt(j)) {
            j++;
         }
         // print result if found
         if (j == m) {
            System.out.println("Oohhoo! Match found at index: " + i);
               return; 
            }
      }
	  // if not found
	  System.out.println("Oopps! No match found");
   }
}
# method to find match
def findMatch(orgText, pattern):
   n = len(orgText)
   m = len(pattern)
   # comparing the text and pattern one by one
   for i in range(n-m+1):
      j = 0
      while j < m and orgText[i+j] == pattern[j]:
         j += 1
      # print result if found
      if j == m:
         print("Oohhoo! Match found at index:", i)
         return 
   # if not found
   print("Oopps! No match found")
# Original Text
orgText = "Tutorials Point"
# pattern to be matched
pattern = "Point"
# method calling
findMatch(orgText, pattern)

Output

Oohhoo! Match found at index: 10

Pattern Searching Algorithms in Data Structure

Various pattern searching techniques can be applied on the data structures to retrieve certain patterns. A pattern searching operation is said to be successful only if it returns the desired element or its index, otherwise, the operation considered as unsuccessful.

Here is the list of pattern searching algorithms that we are going to cover in this tutorial −

Application of Pattern Searching Algorithms

The applications of pattern-searching algorithms are as follows −

  • Bioinformatics − It is a field that applies pattern searching algorithms to analyse biological data, such as DNA and protein structure.
  • Text processing − Text processing involves tasks of finding a string from a collection of documents. It is essential for plagiarism detection, spell and grammar checking, search engine queries, etc.
  • Data Security − Pattern matching algorithms can be used in data security by establishing malware detection and password identification systems.
  • Sentiment analysis − By matching or detecting the tone of words, we can analyse the accent, emotion and sentiment of a user.
  • Recommendation system − We can also analyse the content of a video, audio or any blog through pattern matching algorithms which further help in recommending other content.