資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C語言實現樸素模式匹配演算法
C語言中的模式匹配− 我們需要查詢一個字串是否出現在另一個字串中，例如，字串“algorithm”出現在字串“naive algorithm”中。如果找到，則顯示其位置（即出現的位置）。我們將建立一個接收兩個字元陣列並返回匹配位置（匹配則返回位置，否則返回-1）的函式。
Input: txt = "HERE IS A NICE CAP" pattern = "NICE" Output: Pattern found at index 10 Input: txt = "XYZXACAADXYZXYZX" pattern = "XYZX" Output: Pattern found at index 0 Pattern found at index 9 Pattern found at index 12
我們使用樸素模式搜尋演算法來解決這個問題。此演算法適用於較小的文字。樸素演算法是一種簡單但低效的方法，用於查詢一個字串是否出現在另一個字串中，它逐一檢查字串可能出現的所有位置。
樸素演算法的時間複雜度為O(mn)，其中m是待搜尋模式的大小，n是容器字串的大小。
模式搜尋是計算機科學中一個非常關鍵的問題。無論我們是在記事本/Word檔案中、瀏覽器中、資料庫中還是在某些資訊中搜索字串，都會使用模式搜尋演算法來顯示搜尋結果。
演算法
naive_algorithm(pattern, text)
輸入 − 文字和模式
輸出 − 模式在文字中出現的位置
Start pat_len := pattern Size str_len := string size for i := 0 to (str_len - pat_len), do for j := 0 to pat_len, do if text[i+j] ≠ pattern[j], then break if j == patLen, then display the position i, as there pattern found End
示例
#include <stdio.h>
#include <string.h>
int main (){
char txt[] = "tutorialsPointisthebestplatformforprogrammers";
char pat[] = "a";
int M = strlen (pat);
int N = strlen (txt);
for (int i = 0; i <= N - M; i++){
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M)
printf ("Pattern matches at index %d
", i);
}
return 0;
}輸出
Pattern matches at 6 Pattern matches at 25 Pattern matches at 39
更新於: 2019年12月24日
7K+ 次瀏覽
廣告