検索BJ 1786(KMPアルゴリズム)
13894 ワード
https://www.acmicpc.net/problem/1786
これはKMPアルゴリズムを用いた問題である.
これは、部分的な一致テーブルと2つのポインタを使用して、文字列内で必要な文字列を検索する有効な方法です.
これはKMPアルゴリズムを用いた問題である.
これは、部分的な一致テーブルと2つのポインタを使用して、文字列内で必要な文字列を検索する有効な方法です.
package day0224;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
// KMP 알고리즘(Knuth–Morris–Pratt Algorithm)
// O(N+M)
public class String_KMPTest {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
public static void main(String[] args) throws Exception {
char[] text = br.readLine().toCharArray();
char[] pattern = br.readLine().toCharArray();
int tLength = text.length, pLength = pattern.length;
// 부분일치테이블 만들기 : KMP의 아이디어를 똑같이 적용, W에서 W를 찾는 듯한 행위를 해서...
int[] pi = new int[pLength];
for (int i = 1, j = 0; i < pLength; i++) {// i:접미사 포인터(i=1부터 시작: 우리는 부분일치테이블를 만드는게 목적이므로 첫글자 틀리면 0위치로 가야하므로.),
// j:접두사 포인터
while (j > 0 && pattern[i] != pattern[j])
j = pi[j - 1];
if (pattern[i] == pattern[j])
pi[i] = ++j;
else
pi[i] = 0;
}
int cnt = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
// i : 텍스트 포인터 , j: 패턴 포인터
for (int i = 0, j = 0; i < tLength; ++i) {
while (j > 0 && text[i] != pattern[j])
j = pi[j - 1];
if (text[i] == pattern[j]) { // 두 글자 일치
if (j == pLength - 1) { // j가 패턴의 마지막 인덱스라면
cnt++; // 카운트 증가
list.add((i + 1) - pLength);
j = pi[j];
} else {
j++;
}
}
}
bw.append(cnt + "\n");
if (cnt > 0) {
for (Integer i : list) {
bw.append(Integer.toString(i + 1) + " ");
}
}
bw.flush();
}
}
Reference
この問題について(検索BJ 1786(KMPアルゴリズム)), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/BJ1786-찾기-KMP-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol