on
[LeetCode][Java] 28번 Implement strStr() (문자열, KMP)
[LeetCode][Java] 28번 Implement strStr() (문자열, KMP)
class Solution {
private int KMP( String input, String ptn){
int [] pi = getPi(ptn);
int j = 0 ;
for ( int i = 0 ; i < input. length (); i + + ){
while (j > 0 & & ptn. charAt (j) ! = input. charAt (i))
j = pi[j - 1 ];
if (ptn. charAt (j) = = input. charAt (i)){
if (j = = ptn. length () - 1 )
return i - (ptn. length () - 1 );
else
j + + ;
}
}
return - 1 ;
}
private 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 (j) ! = ptn. charAt (i))
j = pi[j - 1 ];
if (ptn. charAt (j) = = ptn. charAt (i)){
pi[i] = + + j;
}
}
return pi;
}
public int strStr( String haystack, String needle) {
if (needle. length () = = 0 )
return 0 ;
return KMP(haystack, needle);
}
}
from http://aig2029.tistory.com/312 by ccl(A) rewrite - 2021-10-01 07:02:14