[백준][Java] 16916번 부분 문자열 (문자열, KMP)

[백준][Java] 16916번 부분 문자열 (문자열, KMP)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.List; public class Main { private static BufferedReader br = new BufferedReader( new InputStreamReader( System . in )); private static BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System . out )); static List < Integer > li; static int count; private static void KMP( String org, String ptn) { int pi[] = getPi(ptn); int j = 0 ; for ( int i = 0 ; i < org. length (); i + + ) { while (j > 0 & & org. charAt (i) ! = ptn. charAt (j)) { j = pi[j - 1 ]; } if (org. charAt (i) = = ptn. charAt (j)) { if (j = = ptn. length () - 1 ) { count = 1 ; return ; } else j + + ; } } } static int [] getPi( String ptn) { int [] pi = new int [ptn. length ()]; int j = 0 ; for ( int i = 1 ; i < ptn. length (); i + + ) { while (j > 0 & & ptn. charAt (i) ! = ptn. charAt (j)) { j = pi[j - 1 ]; } if (ptn. charAt (i) = = ptn. charAt (j)) pi[i] = + + j; } return pi; } public static void main( String [] args) throws IOException{ String origin = br.readLine(); String pattern = br.readLine(); li = new ArrayList < > (); KMP(origin, pattern); System . out . println (count); // bw.write(""); // bw.flush(); // bw.close(); } // private static int stoi(String input) { // return Integer.parseInt(input); // } } Colored by Color Scripter

from http://aig2029.tistory.com/296 by ccl(A) rewrite - 2021-09-21 05:01:21