한국어
한국어
순진한 알고리즘은 기본적이고 일반적으로 사용되는 문자열 매칭 방법으로 주로 패턴 검색에 사용됩니다. 핵심 아이디어는 텍스트 문자열의 시작 위치에서 시작하여 문자로 문자를 비교하는 것입니다. 문자열의 문자와 패턴 문자열이 동일합니다. 일치하는 경우 정확히 일치하는 하위 문자 또는 텍스트 트래버살이 발견 될 때까지 후속 문자를 계속 비교하십시오.
다음은 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 $에 값을 할당합니다. 외부 루프는 텍스트 문자열의 첫 번째 문자에서 시작하여 최대 $ nm $로 시작하여 후속 비교가 텍스트 길이를 초과하지 않도록합니다.
내부 루프는 텍스트와 패턴 문자열을 문자별로 비교하는 데 사용되며 일치하면 $ j $가 증가합니다. $ j $가 $ m $와 같으면 전체 일치가 발견되고 매치 시작 위치가 반환됩니다.
트래버스 끝에서 일치를 찾을 수없는 경우 함수는 -1을 리턴합니다.
순진한 알고리즘은 주로 텍스트에 지정된 서브 스트링이 포함되어 있는지 여부를 찾는 것과 같은 기본 문자열 일치 문제에 주로 사용됩니다. 예는 다음과 같습니다.
$text = "Hello, world!";
$pattern = "world";
$result = naive_search($text, $pattern);
echo $result; // 산출 7
이 예에서,이 함수는 텍스트에서 기판 "세계"의 위치를 성공적으로 찾아 반환 값이 7입니다.
기본 문자열 일치 외에도 순진한 알고리즘은 정규 표현식 일치, HTML 태그 검색 및 기타 시나리오와 같은 패턴 검색에도 사용할 수 있습니다. 다음 예제는 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); // 산출匹配结果
이 예제는 일반 표현식 및 PHP 내장 기능을 사용하여 HTML에서 링크 태그를 추출하여 패턴 검색의 실제 응용을 보여줍니다.
순진한 알고리즘의 시간 복잡성은 $ o (nm) $이며 여기서 $ n $는 텍스트 길이이고 $ m $는 패턴 길이입니다. 단순하고 직관적 인 구현으로 인해 효율성이 상대적으로 낮지 만 짧은 모드 문자열에는 성능이 허용됩니다. 더 긴 패턴 문자열을 다룰 때는 성능을 향상시키기 위해보다 효율적인 일치 알고리즘을 고려해야합니다.
순진한 알고리즘은 간단하고 효과적인 문자열 일치 방법으로 기본 패턴 검색 메커니즘을 시작하고 이해하기에 적합합니다. 이 기사에서는 PHP 예제를 통해 알고리즘 원칙, 코드 구현 및 응용 프로그램 시나리오를 자세히 설명하여 독자가 마스터 문자열 매칭을위한 실질적인 참조를 제공합니다. 알고리즘에는 성능 제한이 있지만 이해력과 구현의 용이성은 여전히 일부 시나리오에서 유용합니다.
