한국어
한국어
순진한 알고리즘은 기본적이고 직관적 인 문자열 일치 방법으로, 종종 텍스트의 특정 패턴 문자열을 검색하는 데 사용됩니다. 알고리즘은 텍스트와 패턴 문자열의 문자를 텍스트의 첫 번째 문자에서 하나씩 비교하여 텍스트의 일치 위치 또는 끝이 발견되는지 여부를 결정합니다.
다음은 PHP를 사용하여 구현 된 순진한 문자열 일치 알고리즘의 샘플 코드입니다.
function naive_search($text, $pattern) {
$n = strlen($text);
$m = strlen($pattern);
for ($i = 0; $i <= $n - $m; $i++) {
$j = 0;
while ($j < $m && $text[$i + $j] == $pattern[$j]) {
$j++;
}
if ($j == $m) {
return $i;
}
}
return -1;
}
이 함수는 두 개의 문자열 매개 변수를 허용하고 $ 텍스트는 검색 할 텍스트이며 $ 패턴은 일치 해야하는 패턴 문자열입니다. 이 알고리즘은 이중층 루프를 통해 문자 별 텍스트와 패턴 문자를 비교합니다. 경기가 성공하면 첫 번째 발생 위치를 반환하고 일치하지 않으면 -1을 반환합니다.
함수에서 변수 $ n과 $ m은 각각 텍스트의 길이와 패턴을 나타냅니다. 외부 루프는 나머지 부분이 패턴 길이와 일치하기에 충분한 지 확인하기 위해 텍스트의 스캔 범위를 제어합니다. 내부 루프는 경기가 일치하지 않거나 일치가 완료되는 것을 발견 할 때까지 텍스트를 캐릭터별로 비교합니다. 경기가 성공하면 시작 인덱스를 반환합니다. 그렇지 않으면 루프가 끝나면 -1이 반환됩니다.
순진한 알고리즘은 종종 텍스트에 하위 문자열이 있는지 감지하는 것과 같은 간단한 문자열 검색에 사용됩니다. 샘플 코드는 다음과 같습니다.
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // 산출 7
이 예에서 $ 텍스트는 대상 문자열이고 $ 패턴은 찾을 수있는 부분 문자열입니다. 함수 리턴 값은 하위 문자가 먼저 나타나는 위치의 색인입니다.
간단한 문자열 검색 외에도 순진한 알고리즘은 정규 표현식 기반 검색과 같은 패턴 매칭 작업을 도울 수 있습니다. 다음 예제는 HTML 코드에서 모든 링크를 찾는 방법을 보여줍니다.
$html = "<html><body><a href='http://example.com'>Example</a></body></html>";
$pattern = "<a href='(.*?)'>(.*?)</a>";
preg_match_all("/$pattern/s", $html, $matches);
print_r($matches); // 산출匹配结果
이 예에서 정규 표현 패턴은 HTML의 모든 링크를 찾아서 일치하는 배열 결과를 반환하는 데 사용됩니다.
순진한 알고리즘의 시간 복잡성은 O (nm)이며, 여기서 n은 텍스트 길이이고 m은 패턴 길이입니다. 성능이 고급 알고리즘의 성능만큼 좋지는 않지만 구조는 간단하고 이해하고 구현하기 쉽습니다. 짧은 모드 문자열 검색의 경우 성능이 허용됩니다. 그러나 모드 문자열의 길이가 증가함에 따라 효율이 크게 감소하므로 일반적으로 실제 애플리케이션에서보다 효율적인 문자열 검색 알고리즘이 선택됩니다.
가장 기본적인 문자열 일치 알고리즘으로 순진한 알고리즘은 단순하고 직관적 인 구현의 장점을 가지고 있으며 기본 패턴 검색 작업에 적합합니다. 명확한 프로세스를 달성하기 위해 문자 별 텍스트와 패턴 문자를 비교합니다. 효율성 측면에서의 한계에도 불구하고 여전히 많은 실제 애플리케이션, 특히 짧은 모드 문자열을 다루는 시나리오에 대한 실질적인 가치가 있습니다.
