PHP는 패턴 검색을 위한 순진한 알고리즘(문자열 일치 알고리즘)을 구현합니다.

텍스트 txt [0..n-1] 및 패턴 pat [0..m-1]이 주어지면 (char pat [ ], char txt []), txt에서 pat [] []가 나타나는 모든 항목을 인쇄합니다. n>m이라고 가정할 수 있습니다. txt [0..n-1]和模式pat [0..m-1]，编写一个函数搜索（char pat []，char txt []），在txt中打印所有出现的pat [] []。你可以假设n> m。

例子：

输入:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
输出: Pattern found at index 10

输入:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
输出: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

模式（Pattern ）搜索是计算机科学中的一个重要问题。当我们在记事本、 word文件、浏览器或数据库中搜索字符串时，使用模式搜索算法来显示搜索结果。

朴素模式搜索：
将模式逐个滑过文本并检查是否匹配。如果找到匹配项，则再次滑动1以检查后续匹配项。

PHP代码：

<?php 
// 朴素模式搜索算法
  
function search($pat, $txt) 
{ 
    $M = strlen($pat); 
    $N = strlen($txt); 
  
    for ($i = 0; $i <= $N - $M; $i++) 
    { 
  
        // 对于当前索引i，请检查模式匹配
        for ($j = 0; $j < $M; $j++) 
            if ($txt[$i + $j] != $pat[$j]) 
                break; 
  
        // if pat[0...M-1] =  
        // txt[i, i+1, ...i+M-1] 
        if ($j == $M)  
            echo "Pattern found at index ", $i."\n"; 
    } 
} 
  
    $txt = "AABAACAADAABAAABAA"; 
    $pat = "AABA"; 
    search($pat, $txt);

输出：

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13

什么是最好的情况？

当Pattern模式的第一个字符根本不存在于文本中时，会出现最佳情况。

filter_none
brightness_4
txt[] = "AABCCAADDEE"; 
pat[] = "FAA";

最佳情况下的比较次数为O（n）。

什么是最坏的情况？

1）当文本和图案的所有字符相同时。

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

2）当最后一个字符不同时，也会出现最坏情况。

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

最坏情况下的比较次数是O（m *（n-m + 1））

예:

rrreee

패턴 검색은 컴퓨터 과학에서 중요한 문제입니다. 메모장, 단어 파일, 브라우저 또는 데이터베이스에서 문자열을 검색할 때 패턴 검색 알고리즘을 사용하여 검색 결과를 표시합니다. 🎜🎜순진한 패턴 검색:
텍스트 위에 패턴을 하나씩 스와이프하고 일치하는 항목을 확인하세요. 일치하는 항목이 발견되면 1을 다시 밀어 다음 일치 항목을 확인하세요. 🎜🎜PHP 코드: 🎜rrreee🎜출력: 🎜rrreee🎜가장 좋은 시나리오는 무엇인가요? 🎜🎜가장 좋은 경우는 패턴의 첫 번째 문자가 텍스트에 전혀 존재하지 않는 경우입니다. 🎜rrreee🎜최상의 비교 횟수는 O(n)입니다. 🎜🎜최악의 시나리오는 무엇인가요? 🎜🎜1) 텍스트와 패턴의 문자가 모두 동일한 경우. 🎜rrreee🎜2) 마지막 문자가 다른 경우에도 최악의 경우가 발생합니다. 🎜rrreee🎜최악의 비교 횟수는 O(m*(n-m+1))입니다. 반복되는 문자가 포함된 문자열은 영어 텍스트에는 나타나지 않지만 다른 응용 프로그램(예: 이진 텍스트)에는 나타날 가능성이 높습니다. 🎜🎜관련 추천: "🎜PHP 튜토리얼🎜"🎜

위 내용은 PHP는 패턴 검색을 위한 순진한 알고리즘(문자열 일치 알고리즘)을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!