C 中的模式匹配- 我们必须查找一个字符串是否存在于另一个字符串中,例如,字符串“algorithm”存在于字符串“naive algorithm”中。如果是找到,然后显示它的位置(即它所在的位置)。我们倾向于创建一个函数,它接收 2 个字符数组,如果匹配则返回位置,否则返回 -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
我们正在通过朴素模式搜索来解决这个问题。该算法对于较小的文本很有用。 Naive 是一种简单而低效的方法,要查看一个字符串在另一个字符串中出现的位置,就要逐一检查它可能出现的每个位置,以检查它是否存在。
Naive 算法的时间复杂度为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 <p>", i);
}
return 0;
}</p>
输出
'Pattern matches at 6
Pattern matches at 25
Pattern matches at 39