KMP

 

https://chatgpt.com/share/6820120b-9388-800c-9c29-53fa8848b11d

 

static int[] Failure_Function_Computation (String pattern)
{
    int[] failure_func = new int[pattern.length()];
    int prefix_pointer = 0;

    for (int i=1; i<pattern.length(); i++)
    {
        while ( prefix_pointer > 0 && pattern.charAt(prefix_pointer) != pattern.charAt(i) )
            prefix_pointer = failure_func[prefix_pointer-1];

        if ( pattern.charAt(prefix_pointer) == pattern.charAt(i) )
            prefix_pointer++;

        failure_func[i] = prefix_pointer;
    }

    return failure_func;
}

static ArrayList<Integer> KMP (String text, String pattern)
{
    ArrayList<Integer> pattern_pos = new ArrayList<>();
    int[] failure_func = Failure_Function_Computation(pattern);
    int pattern_pointer = 0;

    for (int i=0; i<text.length(); i++)
    {
        while ( pattern_pointer > 0 && text.charAt(i) != pattern.charAt(pattern_pointer) )
            pattern_pointer = failure_func[pattern_pointer-1];

        if ( text.charAt(i) == pattern.charAt(pattern_pointer) )
            pattern_pointer++;

        if ( pattern_pointer == pattern.length() )
        {
            pattern_pos.add(i - pattern_pointer + 1);
            pattern_pointer = failure_func[pattern_pointer-1];
        }
    }

    return pattern_pos;
}

 

 

 

참조

https://chatgpt.com/share/66fdedbe-0dac-800c-9ec6-1f8300fdbfb3

https://bowbowbow.tistory.com/6